2762 helloparty·开车

时间限制: 1 s

空间限制: 32000 KB

题目等级 : 黄金 Gold

题目描述 Description

hellokitty的一个朋友要来他家，但是有很多路，并且一直每一条路的长度，不可能为非正数。而且为整数，求最短路径。已知hellokitty编号为M，朋友家的编号为1

输入描述 Input Description

N+1行

第一行 N M

第二行到第N行表示每一条路的长度。每行三个整数 x y z表示有一条x到y的有向边长度为z

输出描述 Output Description

最短路

样例输入 Sample Input

3 3

1 2 5

2 3 7

1 3 19

样例输出 Sample Output

数据范围及提示 Data Size & Hint

N<=1000

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #include<cstring>
 5 using namespace std;
 6 int n,m,d;
 7 queue<int>s;
 8 int map[1010][1010],dis[1010];
 9 bool vis[1010];
10 void spfa()
11 {
12     memset(dis,0x7f,sizeof(dis));
13     vis[1]=1;
14     s.push(1);
15     dis[1]=0;
16     while(!s.empty() )
17     {
18         d=s.front() ;
19         s.pop() ;
20         for(int i=1;i<=n;++i)
21         {
22             if(map[d][i]!=0&&dis[i]>dis[d]+map[d][i])
23             {
24                 dis[i]=dis[d]+map[d][i];
25                 if(!vis[i])s.push(i); 
26             }
27         }
28         vis[d]=0;
29     } 
30 }
31 int main()
32 {
33     cin>>n>>m;
34     if(n==0)
35     {
36         printf("0");return 0;
37     }
38     for(int a,b,c,i=1;i<=m;++i)
39     {
40         scanf("%d%d%d",&a,&b,&c);
41         map[a][b]=c;
42     }
43     spfa();    
44     printf("%d",dis[n]);
45     return 0;
46 }