Til the Cows Come Home-poj2387(dijkstra判断重边)

题目链接

题目大意:
说的是,一只奶牛位于N号节点,输入N个节点和T对双向的边,求出由N到1的最短的距离,其实就是问的单源最短路问题。

两个点可能有多条路,选择最短的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

const int INF=99999999; //设为无穷大
int maps[1005][1005],v[1005],d[1005]; //v表示是否已经过遍历 d表示从源到点当前最短路
int n;

void Dijkstra(int s,int t)
{
int i,j,k,mini;
for(i=1;i<=n;i++)
d[i]=INF; //除源点设为0距离外 其他先设为无穷大
d[s]=0;
for(i=1;i<=n;i++) //n点循环n次 ,找出n个k,找n个点
{
mini=INF;
k=-1;
for(j=1;j<=n;j++) //在所有未标记点中 选d值最小的点
if(!v[j] && d[j]<mini)
mini=d[k=j];

v[k]=1; //标记节点
if(k==t)
{
printf("%d\n",d[t]);
return;
}
for(j=1;j<=n;j++)
if(!v[j] && (d[k]+maps[k][j])<d[j]) //表示从k出发的点,对于所有边,更新相连点
d[j]=d[k]+maps[k][j];
}
}

int main()
{
int T,i,j,x,y,D;
while(scanf("%d %d",&T,&n)!=EOF)
{
memset(v,0,sizeof(v)); //清除标记
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
maps[i][j]=INF;

for(i=1;i<=T;i++){
scanf("%d%d%d",&x,&y,&D);
if(maps[x][y]>D) //可能有多条路,只记录最短的
maps[x][y]=D,maps[y][x]=D;
}
Dijkstra(1,n);
}
return 0;
}

感谢支持 !
0%