题意
给定\(n\)个点，然后\(m1\)条无向带正权边，\(m2\)条有向且保证无环的带权边（权值可正可负），问\(S\)到所有点到最短路，如果到达不了输出"NO PATH"。
思考
-
无向有权边之间可以形成一个连通块，每个连通块内部可以用\(Dijkstra\)处理相互之间的最短路问题。
有向有权边可以看成每个连通块之间的有向边，那么整个连通块的图就是一个有向无环图。
所以题目问题转化为：利用拓扑序更新前一个连通块到当前连通块的最短路，然后再利用\(Dijkstra\)更新当前连通块内部的最短路。
-
先输入无向边的信息，然后利用 \(dfs\) 将所有点分成许多个连通块，并在 \(vector<int> block[N]\) 中记录每个连通块的点。
-
然后输入有向边的信息，同时将被指向连通块的入度加一。
-
遍历所有连通块，并将入度为0的连通块放入队列中。进行拓扑排序，并对当前连通块进行如下处理：
-
将连通块中的所有点压入优先队列中，等待更新最短路信息。
-
如果当前边的出点和入点处于两个不同连通块，且出点所处连通块的入度等于一，则将出点所处连通块编号入队列。
如果可以利用当前边更新起点到出点到最短距离，则更新为最短距离，且如果两点处于同一连通块，继续放入优先队列，用以更新其他点。
反思
yxc说的很对，这种题目认真思考完，然后码正确之后确实整体的提升要比10道简单题来的更明显。
发现好像图论的问题，都不是难在用什么算法处理上，反而是最开始的分析问题，构建图的模型这个过程让人抓狂，这道题得仔细思考才能发现两种路的性质，此外还有一些很精细的代码细节需要思考，就算我完整码完一遍了，但还是会觉得这个题目我没有掌握，也就是简简单单跟着yxc思考一遍而已，好题！
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 25050;
struct node{
int to,w;
};
vector<node> e[N];
vector<int> block[N];
int dis[N],vis[N];
int id[N],bid;
int n,m1,m2,S;
int in[N];
queue<int> q;
void add(int a,int b,int c) {
e[a].push_back({b,c});
}
void dfs(int u,int now) {
id[u] = now;
block[now].push_back(u);
for(auto i : e[u]) {
if(id[i.to]) continue;
dfs(i.to,now);
}
}
struct ppp{
int val,to;
bool operator<(const ppp& p) const{
return val > p.val;
}
};
void Dij(int x) {
priority_queue<ppp> heap;
for(int i : block[x]) heap.push({dis[i],i});
while(!heap.empty()) {
int u = heap.top().to;heap.pop();
if(vis[u]) continue;
vis[u] = 1;
for(auto i : e[u]) {
int v = i.to,w = i.w;
if(in[id[u]] != in[id[v]] && --in[id[v]] == 0) q.push(id[v]);
if(dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
if(id[u] == id[v]) heap.push({dis[v],v});
}
}
}
}
void Top() {
memset(dis,0x3f,sizeof dis);
dis[S] = 0;
for(int i = 1;i <= bid;++i) {
if(in[i] == 0) q.push(i);
}
while(!q.empty()) {
int u = q.front();q.pop();
Dij(u);
}
}
int main() {
scanf("%d%d%d%d",&n,&m1,&m2,&S);
while(m1--) {
int a,b,c;scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
for(int i = 1;i <= n;++i) {
if(id[i] == 0) {
dfs(i,++bid);
}
}
while(m2--) {
int a,b,c;scanf("%d%d%d",&a,&b,&c);
in[id[b]]++;
add(a,b,c);
}
Top();
for(int i = 1;i <= n;++i) {
if(dis[i] > 0x3f3f3f3f / 2) cout << "NO PATH\n";
else cout << dis[i] << endl;
}
return 0;
}