洛谷 P3008 【USACO11JAN】Roads and Planes G 题解

洛谷 P3008 【USACO11JAN】Roads and Planes G 题解

xiaoh 2020-4-5

题意

给定tt个点,rr条非负权双向边和pp条可能负权的单向边组成的图(1t25000,1p,r500001\leq t\leq 25000,1\leq p,r\leq 50000),且保证若两点间有一条航线单向直接可达,则从终点到起点的路程无论怎么走都无法到达.求从ss点出发的单源最短路.

题解

显然,题意可以理解为:将无向边构成的连通块缩点后构成的新图是DAGDAG.所以考虑将有向图缩点,并进行在DAGDAG上的DPDP.所以我们考虑先标记每个点对应的连通块编号,然后构建一个队列用于储存连通块,并将00入度的点及起点所在连通块压入队列.每次取出队头的连通块进行DijkstraDijkstra优化即可.时间复杂度O(t+p+rlogt)O(t+p+r\log t).

P.S.P.S.由于本题数据很水,所以考虑使用SLFSLF优化可以完美的过去.

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=25010,MAXM=50010;
const long long inf=999999999999;
int n,r,p,s;
int tot=1;
int hd[MAXN],nxt[MAXM*3],edge[MAXM*3];
long long w[MAXM*3];
inline void add_edge(int u,int v,int c)//前向星加边
{
    edge[tot]=v,w[tot]=c;
    nxt[tot]=hd[u],hd[u]=tot++;
}
int c[MAXN];
int cnt=0;
vector<int> rk[MAXN];
void dfs(int p,int val)//深搜处理连通块
{
    if(c[p]) return;
    c[p]=val;
    rk[val].push_back(p);
    for(int i=hd[p];i;i=nxt[i]) dfs(edge[i],val);
}
int ind[MAXN];
queue<int> q;
long long dis[MAXN];
struct node{//Dijkstra专用堆
    int pos;
    long long val;
    friend bool operator < (node a,node b)
    {
        return a.val>b.val;
    }
};
priority_queue<node> q2;
bool book[MAXN];
inline void nopath()
{
    putchar('N'),putchar('O'),putchar(' ');
    putchar('P'),putchar('A'),putchar('T'),putchar('H');
}
int main()
{
    read(n),read(r),read(p),read(s);
    for(int i=1;i<=r;i++)
    {
        int u,v,w;
        read(u),read(v),read(w);
        add_edge(u,v,w),add_edge(v,u,w);
    }
    for(int i=1;i<=n;i++)
    if(!c[i]) dfs(i,++cnt);
    for(int i=1;i<=p;i++)
    {
        int u,v,w;
        read(u),read(v),read(w);
        add_edge(u,v,w);
        ind[c[v]]++;//统计入度
    }
    if(ind[c[s]]) q.push(c[s]);//压入起点所在连通块
    for(int i=1;i<=n;i++) dis[i]=(i==s)? 0:inf;//压入0入度的连通块
    for(int i=1;i<=cnt;i++)
    if(!ind[i]) q.push(i);
    while(!q.empty())
    {
        int tmp=q.front();q.pop();//取出队头的连通块
        for(vector<int>::iterator it=rk[tmp].begin();it!=rk[tmp].end();it++) q2.push({*it,dis[*it]});//执行堆优的Dijkstra
        while(!q2.empty())
        {
            int x=q2.top().pos;q2.pop();
            if(book[x]) continue;
            book[x]=1;
            for(int i=hd[x];i;i=nxt[i])
            if(c[x]==c[edge[i]])
            {
                if(dis[edge[i]]>dis[x]+w[i]) dis[edge[i]]=dis[x]+w[i],q2.push({edge[i],dis[edge[i]]});
            }
            else
            {
                ind[c[edge[i]]]--;
                if(!ind[c[edge[i]]]) q.push(c[edge[i]]);
                dis[edge[i]]=min(dis[edge[i]],dis[x]+w[i]);
            }
        }
    }
    for(int i=1;i<=n;i++)
    if(dis[i]>=999999999) nopath(),putchar('\n');//若距离为inf则为不可达
    else write(dis[i]),putchar('\n');
	return 0;
}