1 //Accepted    4688 KB    63 ms  2 #include <cstdio>  3 #include <cstring>  4 #include <iostream>  5 #include <queue>  6 #include <cmath>  7 #include <algorithm>  8 using namespace std;  9 /** 10   * This is a documentation comment block 11   * 如果有一天你坚持不下去了，就想想你为什么走到这儿！ 12   * @authr songt 13   */ 14 const int imax_n = 1005; 15 const int imax_e = imax_n*imax_n; 16 const int inf=100000000; 17 int head[imax_n]; 18 int next[imax_e]; 19 struct node 20 { 21     int u,v,c; 22     node() 23     { 24  25     } 26     node(int u,int v,int c):u(u),v(v),c(c) 27     { 28  29     } 30 }p[imax_e]; 31 int e; 32 void init() 33 { 34     memset(head,-1,sizeof(head)); 35     memset(next,-1,sizeof(next)); 36     e=0; 37 } 38 void addEdge(int u,int v,int c) 39 { 40     p[e]=node(u,v,c); 41     next[e]=head[u]; 42     head[u]=e++; 43 } 44 int dis[imax_n]; 45 bool vis[imax_n]; 46 int cnt[imax_n]; 47 int n,m; 48 queue<int > q; 49 bool relax(int u,int v,int c) 50 { 51     if (dis[v]>dis[u]+c) 52     { 53         dis[v]=dis[u]+c; 54         return true; 55     } 56     return false; 57 } 58 bool spfa(int src) 59 { 60     while (!q.empty()) q.pop(); 61     memset(vis,false,sizeof(vis)); 62     memset(cnt,0,sizeof(cnt)); 63     for (int i=0;i<=n;i++) 64     dis[i]=inf; 65     dis[src]=0; 66     q.push(src); 67     vis[src]=true; 68     while (!q.empty()) 69     { 70         int pre=q.front(); 71         q.pop(); 72         vis[pre]=false; 73         for (int i=head[pre];i+1;i=next[i]) 74         { 75             if (relax(pre,p[i].v,p[i].c) && !vis[p[i].v]) 76             { 77                 if ((++cnt[p[i].v])>n) return false; 78                 q.push(p[i].v); 79                 vis[p[i].v]=true; 80             } 81         } 82     } 83     return true; 84 } 85 int main() 86 { 87     while (scanf("%d%d",&m,&n)!=EOF) 88     { 89         init(); 90         int u,v,c; 91         for (int i=0;i<m;i++) 92         { 93             scanf("%d%d%d",&u,&v,&c); 94             addEdge(u,v,c); 95             addEdge(v,u,c); 96         } 97         spfa(n); 98         printf("%d\n",dis[1]); 99     }100     return 0;101 }