洛谷 P3008 【USACO11JAN】Roads and Planes G 题解
xiaoh 2020-4-5
题意
给定个点,条非负权双向边和条可能负权的单向边组成的图(),且保证若两点间有一条航线单向直接可达,则从终点到起点的路程无论怎么走都无法到达.求从点出发的单源最短路.
题解
显然,题意可以理解为:将无向边构成的连通块缩点后构成的新图是.所以考虑将有向图缩点,并进行在上的.所以我们考虑先标记每个点对应的连通块编号,然后构建一个队列用于储存连通块,并将入度的点及起点所在连通块压入队列.每次取出队头的连通块进行优化即可.时间复杂度.
由于本题数据很水,所以考虑使用优化可以完美的过去.
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;
}