Problem Description
某省自从实行了很多年的畅通工程计划后,终于修建了很多路。不过路多了也不好,每次要从一个城镇到另一个城镇时,都有许多种道路方案可以选择,而某些方案要比另一些方案行走的距离要短很多。这让行人很困扰。
现在,已知起点和终点,请你计算出要从起点到终点,最短需要行走多少距离。
Input
本题目包含多组数据,请处理到文件结束。
每组数据第一行包含两个正整数N和M(0<N<200,0<M<1000),分别代表现有城镇的数目和已修建的道路的数目。城镇分别以0~N-1编号。
接下来是M行道路信息。每一行有三个整数A,B,X(0<=A,B<N,A!=B,0<X<10000),表示城镇A和城镇B之间有一条长度为X的双向道路。
再接下一行有两个整数S,T(0<=S,T<N),分别代表起点和终点。
Output
对于每组数据,请在一行里输出最短需要行走的距离。如果不存在从S到T的路线,就输出-1.
Sample Input
3 3
0 1 1
0 2 3
1 2 1
0 2
3 1
0 1 1
1 2
Sample Output
2
-1
//Bellman:0ms
#include<stdio.h>
#define INF 1000000000
#define V 205
#define E 1005
int n,m,pre[V],edge[E][3];
int dist[V];
int relax(int u,int v,int c)
{
if(dist[v]>dist[u]+c)
{
dist[v]=dist[u]+c;
pre[v]=u;return 1;
}
return 0;
}
int bellman(int src)
{
int i,j,flag;
for(i=0;i<=n;i++)
{
dist[i]=INF;pre[i]=-1;
}
dist[src]=0;
for(i=0;i<=n;i++)
{
flag=0;
for(j=0;j<2*m;j++)
{
if(1==relax(edge[j][0],edge[j][1],edge[j][2]))
flag=1;
}
if(!flag)break;
}
for(j=0;j<m;j++)
{
if(1==relax(edge[j][0],edge[j][1],edge[j][2]))
return 0;
}
return 1;
}
int main()
{
int start,end,i;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=0;i<2*m;i+=2)
{
scanf("%d%d%d",&edge[i][0],&edge[i][1],&edge[i][2]);
edge[i+1][0]=edge[i][1],edge[i+1][1]=edge[i][0],edge[i+1][2]=edge[i][2];
}
scanf("%d%d",&start,&end);
if(start==end){printf("0\n");continue;}
bellman(start);
if(dist[end]!=INF)
printf("%d\n",dist[end]);
else printf("-1\n");
}
return 0;
}
djikatra:15ms
#include<stdio.h>
#include<string.h>
#define maxn 205
#define INF 1000000000
int matrix[maxn][maxn];
int dist[maxn];
char used[maxn];
int n,m;
void init()
{
int i,j;
memset(used,0,sizeof(used));
for(i=0;i<maxn;i++)
{
for(j=0;j<maxn;j++)
{
matrix[i][j]=i==j?0:INF;
}
}
}
void djikstra(int src)
{
int i,j,min,flag;
for(i=0;i<=n;i++)
dist[i]=matrix[src][i];
used[src]=1,flag=src;
for(i=0;i<=n;i++)
{
min=INF;
for(j=0;j<=n;j++)
{
if(min>dist[j]&&!used[j])
{
min=dist[j];
flag=j;
}
}
used[flag]=1;
for(j=0;j<=n;j++)
{
if(!used[j]&&dist[j]>matrix[flag][j]+dist[flag])
dist[j]=dist[flag]+matrix[flag][j];
}
}
}
int main()
{
int i,u,v,c,src,end;
while(scanf("%d%d",&n,&m)!=EOF)
{
init();
for(i=0;i<m;i++)
{
scanf("%d%d%d",&u,&v,&c);
if(matrix[u][v]>c||matrix[v][u]>c)matrix[u][v]=matrix[v][u]=c;
}
scanf("%d%d",&src,&end);
if(src==end){printf("0\n");continue;}
djikstra(src);
if(dist[end]!=INF)
printf("%d\n",dist[end]);
else printf("-1\n");
}
return 0;
}
floyd 46ms
#include<stdio.h>
#define maxn 205
#define INF 1000000000
int matrix[maxn][maxn];
int n,m;
void init()
{
int i,j;
for(i=0;i<=n;i++)
{
for(j=0;j<=n;j++)
{
matrix[i][j]=i!=j?INF:0;
}
}
}
void floyd()
{
int i,j,k;
for(i=0;i<=n;i++)
{
for(j=0;j<=n;j++)
{
for(k=0;k<=n;k++)
{
if(matrix[j][k]>matrix[j][i]+matrix[i][k])
{
matrix[j][k]=matrix[j][i]+matrix[i][k];
}
}
}
}
}
int main()
{
int u,v,c,start,end,i;
while(scanf("%d%d",&n,&m)!=EOF)
{
init();
for(i=0;i<m;i++)
{
scanf("%d%d%d",&u,&v,&c);
if(matrix[u][v]>c||matrix[v][u]>c)
matrix[u][v]=matrix[v][u]=c;
}
scanf("%d%d",&start,&end);
if(start==end){printf("0\n");continue;}
floyd();
if(matrix[start][end]!=INF)
printf("%d\n",matrix[start][end]);
else printf("-1\n");
}
}
分享到:
相关推荐
题目链接题目意思有n个城镇,编号为0~n-1,m条道路,从一个城镇到另一个城镇有多条路,现在问你从一个城镇到另一个城镇的最短距离是多少。其中要注意的是,城镇之间
算法-畅通工程续(HDU-1874)(包含源程序).rar
NULL 博文链接:https://128kj.iteye.com/blog/1716470
算法-畅通工程(HDU-1232)(包含源程序).rar
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu 1166线段树代码
ACM HDU题目分类,我自己总结的大概只有十来个吧
自己做的HDU ACM已经AC的题目
HDU最全ac代码
hdu动态规划算法集锦