我简单的描述一下题目，题目中所说的有道路和航路：

1.公路是双向的，航路是单向的；

2.公路是正值，航路可正可负；

每一条公路i或者航路i表示成连接城镇A_i（1<=A_i<=T）和B_i（1<=B_i<=T）代价为C_i;每一条公路，C_i的范围为0<=C_i<=10,000；

由于奇怪的运营策略，每一条航路的C_i可能为负的，也就是-10,000<=C_i<=10,000。

数据规模与约定

对于20%的数据，T<=100，R<=500，P<=500；

对于30%的数据，R<=1000，R<=10000，P<=3000；

对于100%的数据，1<=T<=25000，1<=R<=50000，1<=P<=50000。

输入格式

输入的第一行包含四个用空格隔开的整数T，R，P，S。(表示共有T个城镇，R条公路，P条航路，求S点到所有城镇的最短路)

接下来R行，描述公路信息，每行包含三个整数，分别表示A_i，B_i和C_i。

接下来P行，描述航路信息，每行包含三个整数，分别表示A_i，B_i和C_i。

输出格式

输出T行，分别表示从城镇S到每个城市的最小花费，如果到不了的话输出NO PATH。

样例输入

6 3 3 4

1 2 5

3 4 5

5 6 10

3 5 -100

4 6 -100

1 3 -10

样例输出

NO PATH

NO PATH

5

0

-95

-100

讲解：如果数据量比较少的话，很多方法都能做啦，什么Dijkstra，Bellman-ford，Floyd，都能简单的解决了，但是要想得满分，这道题目的数据量太大了，我直接套用的spfa   的模板直接过了，模板不错的，还能保存路径的；

1 #include
       
          2 #include
        
           3 #include
         
            4 #include
          
             5 #include
           
              6 #include
            
              7 #include
             
               8 using namespace std; 9 const int MAXN = 25100; 10 const int INF=0x7FFFFFFF; 11 struct edge 12 { 13 int to,weight; 14 }; 15 int T,R,P,S; 16 vector
              
               adjmap[MAXN];//邻接表 17 bool in_queue[MAXN];//顶点是否在队列中 18 int in_sum[MAXN];//顶点入队的次数 19 int dist[MAXN];//源点到各点的最短路 20 int path[MAXN];//存储到达i的前一个顶点 21 int nodesum; //顶点数 22 int edgesum; //边数 23 bool spfa(int source) 24 { 25 deque< int > dq; 26 int i,j,x,to; 27 for(int i = 1;i<=T;i++)//初始化函数 28 { 29 in_sum[i]= 0; 30 in_queue[i]=false; 31 dist[i]=INF; 32 path[i]=-1; 33 } 34 dq.push_back(source); 35 in_sum[source]++; 36 dist[source]=0; //到达本身的最短距离为0 37 in_queue[source]= true; 38 while(!dq.empty()) 39 { 40 x = dq.front(); 41 dq.pop_front(); 42 in_queue[x]=false; 43 for(int i = 0;i
               
                dist[x]+adjmap[x][i].weight) ) 47 { 48 dist[to] = dist[x]+adjmap[x][i].weight; 49 path[to] = x; 50 if(!in_queue[to]) 51 { 52 in_queue[to] = true; 53 in_sum[to]++; 54 if(in_sum[to] == nodesum) return false; 55 if(!dq.empty()) 56 { 57 if(dist[to]>dist[dq.front()]) dq.push_back(to); 58 else dq.push_front(to); 59 } else dq.push_back(to); 60 } 61 } 62 } 63 } 64 return true; 65 } 66 void print_path(int x) 67 { 68 //输出最小的花费 69 if(dist[x] == INF)//到不了的路径 70 cout<<"NO PATH"<
                

s; 75 // int w = x; 76 // while(path[w]!=-1) 77 // { 78 // s.push(w); 79 // w=path[w]; 80 // } 81 // //以下是经过的路径 82 // while(!s.empty()) 83 // { 84 // cout<

<<" "; 85 // s.pop(); 86 // } 87 // cout<