Time Limit : 3000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 36 Accepted Submission(s) : 25
Problem Description
某省自从实行了非常多年的畅通project计划后，最终修建了非常多路。只是路多了也不好，每次要从一个城镇到还有一个城镇时，都有很多种道路方案能够选择，而某些方案要比还有一些方案行走的距离要短非常多。这让行人非常困扰。
如今，已知起点和终点。请你计算出要从起点到终点，最短须要行走多少距离。
如今，已知起点和终点。请你计算出要从起点到终点，最短须要行走多少距离。
Input
本题目包括多组数据，请处理到文件结束。每组数据第一行包括两个正整数N和M(0<n<200,0<m<1000)，分别代表现有城镇的数目和已修建的道路的数目。
城镇分别以0～n-1编号。 再接下一行有两个整数s,t(0<="S,T<N)，分别代表起点和终点。
</div" 接下来是m行道路信息。
每一行有三个整数a,b,x(0<="A,B<N,A!=B,0<X<10000),表示城镇A和城镇B之间有一条长度为X的双向道路。">
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
#include<stdio.h>
#include<string.h>
#define min(a,b) (a)>(b)?(b):(a)
#define INL 10000000
int x[202][202];
int s[202],d[202];
int n,m,q,r;
void Dijkstra()
{
int min,k;
//for(int i=1;i<=n;i++)
memset(s,0,sizeof(s));
for(int i=0;i<n;i++)
d[i]=INL;
d[q]=0;
while(1)
{ k=-1;
for(int j=0;j<n;j++)
if(s[j]==0&&(k==-1||d[j]<d[k]))
k=j;
if(k==-1)
{
break;
}
s[k]=1;
for(int j=0;j<n;j++)
d[j]=min(d[j],d[k]+x[k][j]);
}
if(d[r]==INL)
printf("-1\n");
else
printf("%d\n",d[r]);
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)//错写成<span style="font-family: Arial, Helvetica, sans-serif;">while(scanf("%d%d",&n,&m)，n|m)</span>
{
int a,b,c,i,j;
for( i=0;i<n;i++)
for( j=0;j<n;j++)
x[i][j]=INL;
for(i=0;i<m;i++)
{
scanf("%d%d%d",&a,&b,&c);
if(x[a][b]>c)
{
x[a][b]=c;
x[b][a]=c;
}
}
scanf("%d%d",&q,&r);
Dijkstra();
}
return 0;
}
再贴一个
#include<stdio.h>
#include<string.h>
#define M 10000000
#define min(a,b) (a)>(b)?(b):(a)
int map[202][202];
int vis[202],dist[202];
int n,s,t;
void dijkstra()
{
int min,i,j,k;
memset(vis,0,sizeof(vis));
for(i=0; i<n; i++)
dist[i]=map[s][i];
dist[s]=0;
while(1)
{
min=M;
for(j=0; j<n; j++)
if(!vis[j]&&dist[j]<min)
{
min=dist[j];
k=j;
}
if(min==M)break;
vis[k]=1;
for(j=0; j<n; j++)
dist[j]=min(dist[j],dist[k]+map[k][j]);
}
if(dist[t]==M)
printf("-1\n");
else
printf("%d\n",dist[t]);
}
int main()
{
int i,j,x,y,z,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=0; i<n; i++)
for(j=0; j<n; j++)
map[i][j]=M; for(i=0; i<m; i++)
{
scanf("%d%d%d",&x,&y,&z); if(map[x][y]>z)
{
map[y][x]=z;
map[x][y]=z;
}
}
scanf("%d%d",&s,&t);
dijkstra();
}
return 0;
}
再贴一个用spfa算法写的。
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
struct stu{
int one,two,val,next;
};
stu edge[30000];
int N,M,d,f;
int head[30000],t,vid[300],dist[300];
void spfa(int s)
{
queue<int> Q;
memset(dist,0x3f3f3f,sizeof(dist));//这个地方出错了错写成 memset(dist,1000000,sizeof(dist));
memset(vid,0,sizeof(vid));
Q.push(s);
dist[s]=0;
vid[s]=1;
while(!Q.empty())
{
int u=Q.front();
Q.pop();
vid[u]=0;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].two;
if(dist[v]>dist[u]+edge[i].val)
{
dist[v]=dist[u]+edge[i].val;
if(!vid[v])
{
vid[v]=1;
Q.push(v);
}
}
}
}
if(dist[f]>1000000)
printf("-1\n");
else
printf("%d\n",dist[f]);
}
void get(int a,int b,int c)
{
stu E={a,b,c,head[a]};
edge[t]=E;
head[a]=t++;
}
int main()
{
while(scanf("%d%d",&N,&M)!=EOF)
{
t=0;
memset(head,-1,sizeof(head));
int a,b,c;
while(M--)
{
scanf("%d%d%d",&a,&b,&c);
get(a,b,c),get(b,a,c);
}
scanf("%d%d",&d,&f);
spfa(d);
}
return 0;
}
再贴一个spfa算法写的代码：
#include<stdio.h>
#include<string.h>
#include<queue>
#define INL 0x3f3f3f3f//有时候写成0x3f3f3f时会出错再加一个3f就正确了。
#include<algorithm>
using namespace std;
struct stu{
int one,two,val,next;
};
stu edge[30000];
int head[30000],t,he,vid[300],vist[300];
void get(int u,int v,int w)
{
stu E={u,v,w,head[u]};
edge[t]=E;
head[u]=t++;
}
void SPFA(int s)
{
queue<int> q;
memset(vist,INL,sizeof(vist));
memset(vid,0,sizeof(vid));
q.push(s);
vist[s]=0;
vid[s]=1;//这个地方错写成vid[s]=0;
while(!q.empty())
{
int u=q.front();
q.pop();
vid[u]=0;//敲代码时这个地方漏掉了
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].two;
if(vist[v]>vist[u]+edge[i].val)
{
vist[v]=vist[u]+edge[i].val;
if(!vid[v])
{
q.push(v);
vid[v]=1;
}
}
}
}
if(vist[he]==INL)//还有一种写法if(vist[he]>100000)
printf("-1\n");
else
printf("%d\n",vist[he]);
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
t=0;
int i,j,k,a,b,c;
memset(head,-1,sizeof(head));//这个出错了
for(i=0;i<m;i++)
{
scanf("%d%d%d",&a,&b,&c);
get(a,b,c);
get(b,a,c);
}
scanf("%d%d",&a,&he);
SPFA(a);
}
return 0;
}