「BZOJ2200」道路与航线

题意：一个 $T$ 个点的图，有 $R$ 条双向边， $P$ 条单向边，单向边权可能为负，但保证途中不存在负环，求起点 $S$ 到各点的最短路。

很明显，带负权边，不能用 $Dijkstra$ ，又因为数据的特殊构造， $SPFA$ 也死了。

仔细看题目，发现“双向边都为非负的”，只有单向边可能为负权，且单向边不会构成环，那么就好办了。

如果只把双向边加到图里，那么会产生几个连通块，把每个连通块看作一个点，再把单向边加入图中，就会得到一个有向无环图，在这个图上，无论边权正负，都可以用拓扑排序扫描，求出最短路。

详细过程如下：

只把双向边加入图中，深搜划分连通块， $bl[x]$ 代表 $x$ 所属连通块的编号；
统计每个连通块的总入度(即有多少条边从连通块外连入连通块内)，记录 $deg[i]$ 为第 $i$ 个连通块的总入度；
建立一个队列(用于拓扑排序)，把最初队列中所有总入度为 $0$ 的连通块编号，包括 $c[S]$ 加入队列，设 $dis[S]=0$ ，其余设为 $+\infty$ 。
取出队头 $i$ ，对这个连通块内部实行 $Dijkstra$ 算法，步骤为：

(1). 建立一个堆，把第 $i$ 个连通块的所有点加入堆；

(2). 从堆中取出 $dis[x]$ 最小的点 $x$ ；

(3). 如果 $x$ 被访问过，回到 (2) ，否则下一步；

(4). 扫描从 $x$ 出发的每条边 $(x,y,z)$ ，用 $dis[x]+z$ 更新 $dis[y]$ ；

(5). 如果 $bl[x]=bl[y]$ ，即在同一个连通块内，把 $y$ 插入堆；

(6). 如果 $bl[x]\neq bl[y]$ ，即不在同一个连通块，则令 $deg[bl[y]]--$ ，如果减到了 $0$ ，就把 $bl[y]$ 加入队列末尾；

(7). 重复以上步骤直到堆为空。
重复步骤 $4$ ，直到队列为空，拓扑序列完成。

$dis$ 数组即为所求。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
int n,m,p,s;
int c[25101],tot,deg[25101];
int head[201010],cnt;
int dis[25101],vis[25101];
queue<int> q;
vector<int> r[25101];
struct node
{
    int next;
    int to;
    int num;
}e[201010];
void add(int from,int to,int num)
{
    e[++cnt].next=head[from];
    e[cnt].to=to;
    e[cnt].num=num;
    head[from]=cnt;
}
void dfs(int u)
{
    c[u]=tot;
    r[tot].push_back(u);
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(c[v])
            continue;
        dfs(v);
    }
}
void dijkstra(int u)
{
    priority_queue< pair<int,int> > d;
    for(int i=0;i<(int)r[u].size();i++)
        d.push(make_pair(-dis[r[u][i]],r[u][i]));
    while(!d.empty())
    {
        int u=d.top().second;
        d.pop();
        if(vis[u])
            continue;
        vis[u]=1;
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].to;
            if(dis[v]>dis[u]+e[i].num)
            {
                dis[v]=dis[u]+e[i].num;
                if(c[u]==c[v])
                    d.push(make_pair(-dis[v],v));
            }
            if(c[u]!=c[v])
            {
                deg[c[v]]--;
                if(!deg[c[v]])
                    q.push(c[v]);
            }
        }
    }
}
void topsort()
{
    for(int i=1;i<=tot;i++)
        if(deg[i]==0)
            q.push(i);
    memset(dis,0x7f,sizeof(dis));
    dis[s]=0;
    q.push(c[s]);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        dijkstra(u);
    }
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&p,&s);
    for(int i=1;i<=m;i++)
    {
        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(!c[i])
        {
            ++tot;
            dfs(i);
        }
    for(int i=1;i<=p;i++)
    {
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        add(a,b,w);
        deg[c[b]]++;//只用统计单向边的入度！！
    }
    topsort();
    for(int i=1;i<=n;i++)
    {
        if(dis[i]<0x3f3f3f3f)
            printf("%d\n",dis[i]);
        else
            printf("NO PATH\n");
    }
    return 0;
}