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 #define inf 10000000 #define ac 250 int map[ac][ac],dist[ac]; int d,e; int cross,road; void floyd() { int i,j,k; for(k=0;kmap[i][k]+map[k][j]) map[i][j]=map[i][k]+map[k][j]; } if(map[d][e]!=inf) printf(%d ,map[d][e]); else printf(-1 ); } int main() { int i,j,a,b,c; while(scanf(%d%d,&cross,&road)!=EOF&&cross!=0&&road!=0) { for(i=0;ic) map[a][b]=map[b][a]=c;//注意是雙向 } scanf(%d%d,&d,&e); floyd(); } }
地傑斯特拉： 代碼：
#include
#include
#define INF 0x3f3f3f
#define max 200+10
int dist[max],visit[max],map[max][max];
int city,road;
int start,end;
void dijkstra()
{
int i,j,next,mindist;
memset(visit,0,sizeof(visit));
for(i=0;idist[j])//尋找距離最短的點
{
mindist=dist[j];
next=j;
}
}
visit[next]=1;
for(j=0;jc)
{
map[x][y]=map[y][x]=c;//雙向
}
}
scanf(%d%d,&start,&end);
dijkstra();
}
return 0;
}
