题意:有n个点,m条无向边(权值非负),k条有向边(权值可能为负数),给定起点s,求出s点到每个点的最短路径长度.(n<=25000,m,k<=50000)
分析:
方法一:既然有负权边,那就跑SPFA咯,但是普通队列SPFA只有88分,要使用到(SLF)的优化策略,即把普通队列改为双端队列,每次要入队时,将dis值与当前队头节点的dis值比较,如果小,则从队头入队,否则从队尾入队.这样就能水过去了.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=50005;
const int M=200005;
int n,r,p,s;
int dis[N],visit[N];
int tot,head[N],nxt[M],to[M],w[M];
inline void add(int a,int b,int c){
nxt[++tot]=head[a];head[a]=tot;
to[tot]=b;w[tot]=c;
}
deque<int>q;
inline void spfa(){
for(int i=1;i<=n;++i)dis[i]=1e9;
q.push_back(s);visit[s]=1;dis[s]=0;
while(q.size()){
int u=q.front();q.pop_front();visit[u]=0;
for(int i=head[u];i;i=nxt[i]){
int v=to[i];
if(dis[v]>dis[u]+w[i]){
dis[v]=dis[u]+w[i];
if(!visit[v]){
if(dis[v]<=dis[q.front()])q.push_front(v);//队头入队
else q.push_back(v);//队尾入队
visit[v]=1;
}
}
}
}
}
int main(){
n=read();r=read();p=read();s=read();
for(int i=1;i<=r;++i){
int a=read(),b=read(),c=read();
add(a,b,c);add(b,a,c);
}
for(int i=1;i<=p;++i){
int a=read(),b=read(),c=read();
add(a,b,c);
}
spfa();
for(int i=1;i<=n;++i){
if(dis[i]==1e9)puts("NO PATH");
else printf("%d
",dis[i]);
}
return 0;
}
方法二:先只把双向边加入图中,则会得到若干个联通块,我们把这些联通块看成一个个"点",那么加入有向边之后就是个(DAG),对于(DAG),我们不用管权值的正负,只要拓扑排序跑就好了.
具体说来,先只把双向边加入图中,跑DFS预处理出每个点属于哪个联通块(belong[]).然后加入有向边,并统计每个联通块的入度(deg[]).把入度为0的联通块和起点S所在的联通块丢进队列里面,开始拓扑排序,对于队列里面的每个节点(联通块),把联通块所包含的点全都丢进堆里面跑(dij).
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=25005;
const int M=200005;
int n,m,k,s,num;
int belong[N],deg[N],dis[N],visit[N];
int tot,head[N],nxt[M],to[M],w[M];
inline void add(int a,int b,int c){
nxt[++tot]=head[a];head[a]=tot;
to[tot]=b;w[tot]=c;
}
vector<int>Q[N];
inline void dfs(int u){
belong[u]=num;Q[num].push_back(u);
for(int i=head[u];i;i=nxt[i]){
int v=to[i];if(belong[v])continue;
dfs(v);
}
}
queue<int>q;
struct ppx{
int id,val;
bool operator <(const ppx &x)const{
return val>x.val;
}
}temp;
priority_queue<ppx>qq;
inline void topsort(){
q.push(belong[s]);//起点所在的联通块丢进队列
for(int i=1;i<=num;++i)if(!deg[i])q.push(i);//入度为0,丢进队列
memset(dis,0x3f,sizeof(dis));dis[s]=0;
while(q.size()){
int u=q.front();q.pop();
for(int j=0;j<Q[u].size();++j){
temp.id=Q[u][j];temp.val=dis[Q[u][j]];
qq.push(temp);
}//把联通块内的所有点丢进堆里
while(qq.size()){//dij模板
temp=qq.top();qq.pop();
int uu=temp.id;
if(visit[uu])continue;visit[uu]=1;
for(int i=head[uu];i;i=nxt[i]){
int vv=to[i];
if(dis[vv]>dis[uu]+w[i]){
dis[vv]=dis[uu]+w[i];
if(belong[uu]==belong[vv]){
temp.id=vv;temp.val=dis[vv];
qq.push(temp);
}
}
if(belong[uu]!=belong[vv]){//维护拓扑排序
--deg[belong[vv]];
if(!deg[belong[vv]])q.push(belong[vv]);
}
}
}
}
}
int main(){
n=read();m=read();k=read();s=read();
for(int i=1;i<=m;++i){
int a=read(),b=read(),c=read();
add(a,b,c);add(b,a,c);//先只建无向边
}
for(int i=1;i<=n;++i)if(!belong[i])++num,dfs(i);//预处理联通块
for(int i=1;i<=k;++i){
int a=read(),b=read(),c=read();
add(a,b,c);++deg[belong[b]];//加入有向边,并统计每个联通块的入度
}
topsort();//拓扑排序
for(int i=1;i<=n;++i){
if(dis[i]>1e9)puts("NO PATH");//刚开始写dis[i]==1e9,只有30分,奇怪!!!
else printf("%d
",dis[i]);
}
return 0;
}