解法一
看数据范围,以及一点分析,能够确定这是单源最短路,可选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; }
后话
好像不太会用格式。如果对内容或是格式有些许不适,还请指出(^▽^)