5778: 城市路 dijstra-526互联

描述

罗老师被邀请参加一个舞会，是在城市n，而罗老师当前所处的城市为1,附近还有很多城市2~n-1，有些城市之间没有直接相连的路，有些城市之间有直接相连的路，这些路都是双向的，当然也可能有多条。

现在给出直接相邻城市的路长度，罗老师想知道从城市1到城市n，最短多少距离。

输入

输入n, m，表示n个城市和m条路;

接下来m行，每行a b c，表示城市a与城市b有长度为c的路。

输出

输出1到n的最短路。如果1到达不了n，就输出-1。

样例输入

5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100

样例输出

提示

【数据规模和约定】

1≤n≤2000

1≤m≤10000

0≤c≤10000

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N = 2005,inf = 1e9;
 4 int vis[N],dis[N],g[N][N];
 5 int n,m,w;
 6 void dijstra()
 7 {
 8     for(int i=1;i<=n;i++)dis[i] = g[1][i];
 9     dis[1] = 0;
10     vis[1] = 1;
11     int pos,minn;
12     for(int i=1;i<=n;i++)
13     {
14         minn = inf;
15         for(int j=1;j<=n;j++)
16         {
17             if(!vis[j] && minn>dis[j])
18             {
19                 pos = j;//找到从1出发可以到达的最短的点j 
20                 minn = dis[j];
21             }
22         }
23         vis[pos] = 1; //出发去j，标记上 
24         for(int j=1;j<=n;j++)
25         {
26             if(dis[j]>dis[pos]+g[pos][j]) //如果1到j的距离比到达最短的点pos的距离+pos到j的距离远，那就更新替换 
27             {
28                 dis[j] = dis[pos]+g[pos][j];
29             }
30         }
31     } 
32 }
33 int main()
34 {
35     cin>>n>>m;
36     memset(g,127,sizeof(g));
37     for(int i=1;i<=m;i++)
38     {
39         int x,y,z;
40         cin>>x>>y>>z;
41         if(z<g[x][y])g[x][y] = g[y][x] = z;
42     }
43     dijstra();
44     if(dis[n]<inf)cout<<dis[n];
45     else cout<<-1;
46      return 0;
47 }