道路与航线

连通负权图最短路 T4 农夫约翰正在一个新的销售区域对他的牛奶销售方案进行调查。

他想把牛奶送到 $T$ 个城镇，编号为 $1\sim T$。

这些城镇之间通过 $R$ 条道路 (编号为 $1$ 到 $R$) 和 $P$ 条航线 (编号为 $1$ 到 $P$) 连接。

每条道路 $i$ 或者航线 $i$ 连接城镇 $A_i$ 到 $B_i$，花费为 $C_i$。

对于道路，$0\le C_i\le 10,000$;然而航线的花费很神奇，花费 $C_i$ 可能是负数($-10,000\le C_i\le 10,000$)。

道路是双向的，可以从 $A_i$ 到 $B_i$，也可以从 $B_i$ 到 $A_i$，花费都是 $C_i$。

然而航线与之不同，只可以从 $A_i$ 到 $B_i$。

事实上，由于最近恐怖主义太嚣张，为了社会和谐，出台了一些政策：保证如果有一条航线可以从 $A_i$ 到 $B_i$，那么保证不可能通过一些道路和航线从 $B_i$ 回到 $A_i$。

由于约翰的奶牛世界公认十分给力，他需要运送奶牛到每一个城镇。

他想找到从发送中心城镇 $S$ 把奶牛送到每个城镇的最便宜的方案。

输入格式

第一行包含四个整数 $T,R,P,S$。

接下来 $R$ 行，每行包含三个整数（表示一个道路）$A_i,B_i,C_i$。

接下来 $P$ 行，每行包含三个整数（表示一条航线）$A_i,B_i,C_i$。

输出格式

第 $\mathrm{1..}T$ 行：第 $i$ 行输出从 $S$ 到达城镇 $i$ 的最小花费，如果不存在，则输出 NO PATH。

数据范围

$1\le T\le 25000$,
$1\le R,P\le 50000$,
$1\le A_i,B_i,S\le T$

输入样例：

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来求解最短路, 而链接各连通块的边有可能为负, 但题目中不存在自环。相比于用spfa最坏情况下$O(NM)$, 不如在连通块内用dijkstra的$O(M\log N)$, 连通块之间根据拓扑排序来DP求最短路。

总时间复杂度为 ${\sum }_{i=1}^k{m}_i\log n_i$ , 把 $\log n_i$ 放缩为 $\log n$, 再提出来, 这样时间复杂度就是 $O(M\log N)$。

代码流程为： 先处理道路, 定义 id[N] 为当前点在哪个连通块中, bcnt 为连通块数量, block[i][N] 为某个连通块 i 内的点。 然后读入航线, 同时记录连通块的入度。 接着先把入度为0的连通块加入到队列中, 用循环来处理队列, 对每个连通块进行dijkstra操作。 dijkstra更新时, 只更新在当前连通块的点。 在更新时把不在该连通块的点, 所在的连通块入度减一, 并把此时入度为0的连通块加入到队列中。 最后的dist数组就是答案。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;
const int N = 3e4, M = 2e5 + 10, INF = 0x3f3f3f3f;
typedef pair<int,int> PII;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
bool st[N];
vector<int> block[N];
int id[N], bcnt;
int din[N];
int n,m, mr,s;
queue<int> q;
 
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
 
void dfs(int x, int bid)
{
    id[x] = bid;
    block[bid].push_back(x);
    for(int i = h[x]; ~i; i = ne[i])
    {
        int j = e[i];
        if(!id[j])
            dfs(j, bid);
    }
}
 
void dijkstra(int bid)
{
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    memset(st, 0, sizeof st);
    for(int i = 0; i < block[bid].size(); i++) heap.push({dist[block[bid][i]], block[bid][i]});
    
    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();
        
        int ver = t.second;
        if(st[ver]) continue;
        st[ver] = true;
        
        for(int i = h[ver]; ~i; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                if(id[ver] == id[j])
                    heap.push({dist[j], j});
            }
            
            if(id[ver] != id[j] && -- din[id[j]] == 0) q.push(id[j]);
        }
    }
}
 
 
 
void topsort()
{
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;
    
    for(int i = 1; i <= bcnt; i++)
        if(!din[i]) q.push(i);
    
    while(q.size())
    {
        int t = q.front();
        q.pop();
        dijkstra(t);
    }
}
 
int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m >> mr >> s;
    while(m--)
    {
        int a, b , c;
        cin >> a >> b >> c;
        add(a,b,c);
        add(b,a,c);
    }
    // 标记连通块
    for(int i = 1; i <= n; i++)
        if(!id[i])
            dfs(i, ++bcnt);
    
    while(mr--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a,b,c);
        din[id[b]]++;
    }
    
    topsort();
    
    for(int i = 1; i <= n; i++)
    {
        if(dist[i] > INF / 2) cout << "NO PATH\n";
        else cout << dist[i] << endl;
    }
    
    return 0;
}