道路与航线

道路和航线

https://ac.nowcoder.com/acm/problem/50381

解法一

看数据范围，以及一点分析，能够确定这是单源最短路，可选DJ与SPFA，但是图中存有负权边，只能SPFA了。

However

so，这里要用一个江湖人称“SLF”的优化，即当前节点到起点距离小于队首的时候，将此点插入队首，否则，正常插入队尾。感觉这种优化可能被用到的机会很少，但很可能正好解决掉了专门卡spfa的数据以及网格图。

解法一代码

#include<deque>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
using namespace std;
const int N=4e5+10;
int n,m1,m2,s,tot;
int h[N],nex[N],ver[N],pri[N],vis[N],dis[N];
inline void add(int x,int y,int z)
{
nex[tot]=h[x];
ver[tot]=y;
pri[tot]=z;
h[x]=tot++;
}
inline void spfa(int s)
{
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
deque<int>q;
dis[s]=0;vis[s]=1;
q.push_back(s);
while(q.size())
{
 int now=q.front();q.pop_front();
 vis[now]=0;
 for (int i=h[now];~i;i=nex[i])
 {
     int j=ver[i];
     if(dis[j]>dis[now]+pri[i])
     {
         dis[j]=dis[now]+pri[i];
         if(!vis[j])
         {
             vis[j]=1;
             if(q.size()&&dis[j]<dis[q.front()]) q.push_front(j);
             else q.push_back(j);
         }
     }
 }
}
}
int main()
{
memset(h,-1,sizeof(h));
scanf("%d%d%d%d",&n,&m1,&m2,&s);
for (int i=1;i<=m1;i++)
{
 int x,y,z;
 scanf("%d%d%d",&x,&y,&z);
 add(x,y,z),add(y,x,z);
}
for (int i=1;i<=m2;i++)
{
 int x,y,z;
 scanf("%d%d%d",&x,&y,&z);
 add(x,y,z);
}
spfa(s);
for (int i=1;i<=n;i++)
{
 if(dis[i]==0x3f3f3f3f) puts("NO PATH");
 else printf("%d\n",dis[i]);
}
return 0;
}

解法二

注意到道路权值为正，航线权值为负，且有向边不会构成一个环，那么可以根据拓扑排序的思想，把每一个有道路连接的小镇归为一个连通块，然后在每一个联通块中连边，就能构成一个有向连通图，然后能在规定时间内跑出单源最短路，比解法一更快

解法二代码

#include<bits/stdc++.h>
using namespace std;
const int N=3e4+10,M=2e5+10;
int n,m1,m2,s,num,dfn;
int h[N],bel[N],deg[N],dis[N];
bool vis[N];
struct nk
{
int val,pos;
bool operator < (const nk &b)const
{
 return val>b.val;
}
};
struct E {int nex,to,dis;}e[M];
vector<int>c[N];
queue<int>q;
inline void add(int u,int v,int w)
{
e[++num].nex=h[u];
e[num].to=v;
e[num].dis=w;
h[u]=num;
}
inline void dfs(int x)
{
bel[x]=dfn,vis[x]=1;
c[dfn].push_back(x);
for(int i=h[x];i;i=e[i].nex)
{
 int j=e[i].to;
 if(vis[j]) continue;

 dfs(j);
}
}
inline void dj(int id)
{
priority_queue<nk>p;
int len=c[id].size();
for(int i=0;i<len;i++)
 p.push((nk){dis[c[id][i]],c[id][i]});
while(p.size())
{
 int now=p.top().pos;p.pop();

 if(vis[now]) continue;
 vis[now]=1;
 for(int i=h[now];i;i=e[i].nex)
 {
     int j=e[i].to,w=e[i].dis;
     if(dis[now]+w<dis[j])
     {
         dis[j]=dis[now]+w;
         if(bel[now]==bel[j]) p.push((nk){dis[j],j});
     }
     deg[bel[j]]--;
     if(!deg[bel[j]]&&bel[now]!=bel[j]) q.push(bel[j]);
 }
}
}
int main()
{
scanf("%d%d%d%d",&n,&m1,&m2,&s);
for (int i=1;i<=m1;i++)
{
 int x,y,z;scanf("%d%d%d",&x,&y,&z);
 add(x,y,z),add(y,x,z);
}
//道路
for (int i=1;i<=n;i++)
 if(!vis[i]) ++dfn,dfs(i);
//划分一个连通块 
for (int i=1;i<=m2;i++)
{
 int x,y,z;
 scanf("%d%d%d",&x,&y,&z);
 add(x,y,z);deg[bel[y]]++;
}
//航线 
memset(vis,0,sizeof(vis));
memset(dis,0x3f,sizeof(dis));
dis[s]=0,q.push(bel[s]);
for(int i=1;i<=dfn;i++) if(!deg[i]) q.push(i);
while(q.size())
{
 int now=q.front();
 q.pop();dj(now);
}
for (int i=1;i<=n;i++)
{
 if(dis[i]>=1e9) printf("NO PATH\n");
 else printf("%d\n",dis[i]);
}
return 0; 
}