算法竞赛进阶指南，357页，最短路径，拓扑排序
本题要点：
1、因为图有负权，不能只用dijkstra 来处理。直接用 spfa 算法，本题的数据会超时。
2、本题中，双向的道路是正数，而单向的航班，有可能是负权。如果在图中只加道路，那么图会分为几个连通块，
对于块内的点，通过堆优化的dijkstra算法更新最短路；
3、 把连通块的所有点都缩为一个点，再添加航路，则图变成了一个有向无环图，可以按拓扑顺序扫描，
线性时间求出最短路径。
4、 具体步骤：
a）求出每个点所在的连通块编号（c[i]）, 统计每个连通块的总入度（deg[i]）
b）建立一个队列 q（存放的是每个连通块的编号）， 先把源点所在的连通块编号入队（c[st]）, 再把所有总入度为0
的连通块编号入队。设d[st] = 0, 其余为 无穷大。
c）每次从队列 q中出队一个连通块的编号，对该连通块执行 dijkstra 算法（用堆优化），
扫描从x出发的所有边(x, y, z), 用 d[x] + z 去更新d[y],
如果 c[x] == c[y] (同一个连通块内)， 把y插入堆;
如果 c[x] != c[y] (不在同一个连通块内)， --deg[c[y]]， 如果总入度为0，则把该连通块编号插入队列q的末尾
5、用 vector 存放每个连通块内的所有的节点编号（可以避免每次把某个连通块内的所有节点加入堆中，全盘扫描图中的所有节点）
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int MaxN = 25010, MaxM = 150010, INF = 0x3f3f3f3f;
int head[MaxN], ver[MaxM], Next[MaxM], edge[MaxM], d[MaxN];
int n, r, f, st, tot, block_cnt; // block_cnt连通块编号
bool vis[MaxN];
int c[MaxN]; //c[i]表示节点 i所在的连通块的编号
int deg[MaxN]; //第i个连通块的入度
vector <int> block[MaxN];void add(int x, int y, int z)
{
ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;
} void dfs(int x)
{
c[x] = block_cnt;block[block_cnt].push_back(x);for(int i = head[x]; i; i = Next[i]){
int y = ver[i];if(!c[y]){
dfs(y);}}
}void solve()
{
memset(d, 0x7f, sizeof d);memset(vis, false, sizeof vis);d[st] = 0;queue<int> q; //存放连通块的编号q.push(c[st]);for(int i = 1; i <= block_cnt; ++i) //把入度为0的连通块编号全部加入 队列{
if(!deg[i]) {
q.push(i); }}while(q.size()){
int id = q.front(); q.pop();priority_queue<pair<int , int> > pq; //某个连通块int len = block[id].size();for(int i = 0; i < len; ++i){
int indx = block[id][i];pq.push(make_pair(-d[indx], indx));}while(pq.size()){
int x = pq.top().second; pq.pop();if(vis[x]) continue;vis[x] = true;for(int i = head[x]; i; i = Next[i]){
int y = ver[i], z = edge[i];if(d[y] > d[x] + z){
d[y] = d[x] + z;if(c[x] == c[y]){
pq.push(make_pair(-d[y], y));}}if(c[x] != c[y] && !--deg[c[y]]){
q.push(c[y]); }}}}for(int i = 1; i <= n; ++i){
if(d[i] > INF){
printf("NO PATH\n");}else{
printf("%d\n", d[i]);}}
}int main()
{
scanf("%d%d%d%d", &n, &r, &f, &st);int x, y, z;for(int i = 0; i < r; ++i){
scanf("%d%d%d", &x, &y, &z);add(x, y, z);add(y, x, z);}for(int i = 1; i <= n; ++i){
if(!c[i]){
++block_cnt;dfs(i); }}for(int i = 0; i < f; ++i){
scanf("%d%d%d", &x, &y, &z);add(x, y, z);deg[c[y]]++;}solve();return 0;
}/* 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 */