BZOJ_2200
这个题目一看就知道SPFA可做，但是SPFA就是超时……
USACO上给出的解法的大致意思是：由于每条航线都是单向的，而且不存在从航线的终点辗转到航线起点的通路，那么就是说航线将原图分成了若干个相对封闭的区域，我们把航线从原图中拿掉后，剩下的就应当是若干个连通块。由于每个连通块中只有非负权边，那么我们就可以在连通块内用Dijkstra求最短路了。而且从S开始做最短路时，这些连通块是有一定的拓扑关系的，也就是说只有先确定了S到某些连通块中的点的最短路，才能确定S到另一些连通块中的点的最短路，这样按连通块的拓扑顺序，一个连通块一个连通块的不断地求最短路，就可以得到S到每个点的最短路了。
#include#include #include #include #define MAXD 25010#define INF 0x3f3f3f3fstruct Edge{ int v, c; Edge(){} Edge(int _v, int _c) : v(_v), c(_c){}};std::vector road[MAXD], fly[MAXD];int T, R, P, S;void init(){ int x, y, c; for(int i = 1; i <= T; i ++) road[i].clear(), fly[i].clear(); for(int i = 0; i < R; i ++) { scanf("%d%d%d", &x, &y, &c); road[x].push_back(Edge(y, c)), road[y].push_back(Edge(x, c)); } for(int i = 0; i < P; i ++) { scanf("%d%d%d", &x, &y, &c); fly[x].push_back(Edge(y, c)); }}int p[MAXD], dgr[MAXD], dis[MAXD], cal[MAXD];struct St{ int id, v; St(){} St(int _id, int _v) : id(_id), v(_v){} bool operator < (const St &t) const { return v > t.v; }};int find(int x){ return p[x] == x ? x : (p[x] = find(p[x]));}void bfs(){ memset(dgr, 0, sizeof(dgr[0]) * (T + 1)); std::queue q; memset(cal, 0, sizeof(cal[0]) * (T + 1)); cal[S] = 1, q.push(S); while(!q.empty()) { int x = q.front(); q.pop(); for(int i = 0; i < road[x].size(); i ++) { int y = road[x][i].v; if(!cal[y]) cal[y] = 1, q.push(y); } for(int i = 0; i < fly[x].size(); i ++) { int y = fly[x][i].v; ++ dgr[find(y)]; if(!cal[y]) cal[y] = 1, q.push(y); } }}void dij(int set, std::queue &wait, std::vector ini[]){ std::priority_queue q; for(int i = 0; i < ini[set].size(); i ++) { int x = ini[set][i]; q.push(St(x, dis[x])); } while(!q.empty()) { St st = q.top(); q.pop(); int x = st.id; if(cal[x]) continue; cal[x] = 1; for(int i = 0; i < road[x].size(); i ++) { int y = road[x][i].v, c = road[x][i].c; if(dis[x] + c < dis[y]) dis[y] = dis[x] + c, q.push(St(y, dis[y])); } for(int i = 0; i < fly[x].size(); i ++) { int y = fly[x][i].v, c = fly[x][i].c, set = find(y); -- dgr[set]; if(dgr[set] == 0) wait.push(set); if(dis[x] + c < dis[y]) dis[y] = dis[x] + c, ini[set].push_back(y); } }}void solve(){ for(int i = 1; i <= T; i ++) p[i] = i; for(int i = 1; i <= T; i ++) for(int j = 0; j < road[i].size(); j ++) { int x = find(i), y = find(road[i][j].v); if(x != y) p[x] = y; } bfs(); std::vector ini[MAXD]; std::queue wait; memset(dis, 0x3f, sizeof(dis[0]) * (T + 1)); dis[S] = 0, ini[find(S)].push_back(S), wait.push(find(S)); memset(cal, 0, sizeof(cal[0]) * (T + 1)); while(!wait.empty()) { int set = wait.front(); wait.pop(); dij(set, wait, ini); } for(int i = 1; i <= T; i ++) { if(dis[i] == INF) printf("NO PATH\n"); else printf("%d\n", dis[i]); }}int main(){ while(scanf("%d%d%d%d", &T, &R, &P, &S) == 4) { init(); solve(); } return 0;}