poj1734
Time Limit: 1000MS | Memory Limit: 65536K | |||
Total Submissions: 9078 | Accepted: 3380 | Special Judge |
Description
In the town there are N crossing points numbered from 1 to N and M two-way roads numbered from 1 to M. Two crossing points can be connected by multiple roads, but no road connects a crossing point with itself. Each sightseeing route is a sequence of road numbers y_1, ..., y_k, k>2. The road y_i (1<=i<=k-1) connects crossing points x_i and x_{i+1}, the road y_k connects crossing points x_k and x_1. All the numbers x_1,...,x_k should be different.The length of the sightseeing route is the sum of the lengths of all roads on the sightseeing route, i.e. L(y_1)+L(y_2)+...+L(y_k) where L(y_i) is the length of the road y_i (1<=i<=k). Your program has to find such a sightseeing route, the length of which is minimal, or to specify that it is not possible,because there is no sightseeing route in the town.
Input
Output
Sample Input
5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20
Sample Output
1 3 5 2
Source
#include<iostream>
#include<cstring>
using namespace std;
int n,m,ans=0x3f3f3f3f,s,t,temk=0x3f3f3f3f,cnt;
const int maxn=;
int a[maxn][maxn],d[maxn][maxn],f[maxn][maxn],path[maxn];
void dfs(int i,int j){
if(f[i][j]==){path[++cnt]=j;return;}
dfs(f[i][j],j);
}
void floy(){
memset(path,,sizeof(path));
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
d[i][j]=a[i][j];
for(int k=;k<=n;k++){
for(int i=;i<k;i++)
for(int j=i+;j<k;j++)
if((long long)a[i][k]+a[k][j]+d[i][j]<ans){//注意数据类型,3个连加,容易超Int
ans=a[i][k]+a[k][j]+d[i][j];
s=i;t=j;
temk=k;
cnt=;
path[++cnt]=s;
dfs(s,t);//记录从s到t的中间节点,包含t,不含s.
path[++cnt]=k; } for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
if(d[i][j]>d[i][k]+d[k][j]){
d[i][j]=d[i][k]+d[k][j];
f[i][j]=k;
}
}
return ;
}
int main(){
memset(a,0x3f,sizeof(a));
memset(f,,sizeof(f));
cin>>n>>m;
for(int i=;i<=n;i++) a[i][i]=;
for(int i=;i<=m;i++){
int x,y,w;
cin>>x>>y>>w;
if(w<a[x][y]){
a[x][y]=a[y][x]=w;
}
}
floy();
if(temk==0x3f3f3f3f)cout<<"No solution."<<endl;
else {for(int i=;i<=cnt;i++) cout<<path[i]<<' ';cout<<endl;}
return ;
}
最新文章
- C++随笔:从Hello World 探秘CoreCLR的内部(1)
- C# 6.0的属性(Property)的语法与初始值
- Linux - Yum的常用方法总结
- Android View之用户界面...
- 深入理解JavaScript中的this关键字
- PHP表单常用正则表达式(URL、HTTP、手机、邮箱等)
- C语言中一些非常酷的技巧(cool tricks)
- Windows Mobile 常用键值VK对应表
- HttpWebRequest操作已超时
- open live writer实现多博客同步发送
- 永续公债(or统一公债)的麦考利久期(Macaulay Duration)的计算
- SystemCheckError: System check identified some issues: ERRORS: users.Test.groups: (fields.E304) Reverse accessor for &#39;Test.groups&#39; clashes with reverse accessor for &#39;User.groups&#39;.
- idea2018.1.5激活教程
- 5.IAP - FLASH
- grep 正则匹配
- JMeter学习(十一)WebSerivice测试计划(转载)
- HDU Bomb Game 3622 (2-Sat)
- CUDA C Programming Guide 在线教程学习笔记 Part 1
- Spring Boot&mdash;11控制器Controller
- 关于mybatis中一级缓存和二级缓存的简单介绍
热门文章
- 获取select标签的自定义属性
- openstack安装部署——计算服务(控制节点&;计算节点)前言
- 你应该使用Python3里的这些新特性
- 成功解决 AttributeError: module &#39;tensorflow.python.keras.backend&#39; has no attribute &#39;get_graph&#39;
- Euler&#39;s Sum of Powers Conjecture
- 从c到c++<;四>;
- c++对象模型和RTTI(runtime type information)
- ZZNUOJ-2155-单身man集合-【标程做法:数位DP-1-10^8,提前暴力打表法: 砍时间复杂度到10^5】
- Elasticsearch: nested对象
- springboot2.0入门(八)-- profile启动文件配置