差分约束第一题，想明白以后就可以建图了。由于此题数据特殊，队列优化的spfa会超时，可以改成用栈来优化。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6  7 const int INF = 9999999; 8 const int N = 30001; 9 const int M = 150000;10 int head[N];11 int dist[N];12 bool visit[N];13 int n, m, e;14 15 struct Edge16 {17     int v, next, w;18 } edge[M];19 20 void addEdge( int u, int v, int w )21 {22     edge[e].v = v;23     edge[e].w = w;24     edge[e].next = head[u];25     head[u] = e++;26 }27 28 void spfa( int s )29 {30     for ( int i = 1; i <= n; i++ )31     {32         dist[i] = INF;33         visit[i] = false;34     }35     dist[s] = 0;36     visit[s] = true;37     int q[N], top = 0;38     q[top++] = s;39     while ( top )40     {41         int u = q[--top];42         visit[u] = false;43         for ( int j = head[u]; j != -1; j = edge[j].next )44         {45             int v = edge[j].v, w = edge[j].w;46             if ( dist[v] > dist[u] + w )47             {48                 dist[v] = dist[u] + w;49                 if ( !visit[v] )50                 {51                     q[top++] = v;52                     visit[v] = true;53                 }54             }55         }56     }57 }58 59 int main ()60 {61     while ( scanf("%d%d", &n, &m) != EOF )62     {63         e = 0;64         memset( head, -1, sizeof(head) );65         while ( m-- )66         {67             int u, v, w;68             scanf("%d%d%d", &u, &v, &w);69             addEdge( u, v, w );70         }71         spfa(1);72         printf("%d\n", dist[n]);73     }74     return 0;75 }