题目描述
农夫约翰正在一个新的销售区域对他的牛奶销售方案进行调查。
他想把牛奶送到T个城镇,编号为1~T。
这些城镇之间通过R条道路 (编号为1到R) 和P条航线 (编号为1到P) 连接。
每条道路i或者航线i连接城镇Ai到Bi,花费为Ci。
对于道路,0≤Ci≤10,000;然而航线的花费很神奇,花费Ci可能是负数(−10,000≤Ci≤10,000)。
道路是双向的,可以从Ai到Bi,也可以从Bi到Ai,花费都是Ci。
然而航线与之不同,只可以从Ai到Bi。
事实上,由于最近恐怖主义太嚣张,为了社会和谐,出台了一些政策保证:如果有一条航线可以从Ai到Bi,那么保证不可能通过一些道路和航线从Bi回到Ai。
由于约翰的奶牛世界公认十分给力,他需要运送奶牛到每一个城镇。
他想找到从发送中心城镇S把奶牛送到每个城镇的最便宜的方案。
输入格式
第一行包含四个整数T,R,P,S。
接下来R行,每行包含三个整数(表示一个道路)Ai,Bi,Ci。
接下来P行,每行包含三个整数(表示一条航线)Ai,Bi,Ci。
输出格式
第1..T行:第i行输出从S到达城镇i的最小花费,如果不存在,则输出“NO PATH”。
数据范围
1≤T≤25000,
1≤R,P≤50000,
1≤Ai,Bi,S≤T,
输入样例:
6 3 3 4
1 2 5
3 4 5
5 6 10
3 5 -100
4 6 -100
1 3 -10
输出样例:
NO PATH
NO PATH
5
0
-95
-100
解题报告
题意理解
一道明显的单源最短路…
思路解析
首先看到这道题目,我们发现这道题目的复杂度,首先确定了是O(nlogn)级别的,所以说,我们的算法初步确定在dijskra和SPFA上面.
但是我们发现这道题目一个关键点,就是题目中出现了负权边.
一旦出现了负权边,那么我们只能使用SPFA.lyd大佬的算法过于复杂,我们还是来点容易的水水过去吧
但是对于USACO的题目而言,我们发现他们居然恶心地卡SPFA算法,那么我们不得不使用一些玄学优化.
对于SPFA算法而言,它的优化有两种,我们今天使用SLF优化算法.
众所周知,SPFA算法是一种鉴于队列的实现算法.每一次有节点加入队列都是加入队尾.
但是SLF优化,不同于一般的SPFA算法,它是一种利用双端队列算法处理的问题.
如果说当前点所花费的值少于我们当前队头点的值的话,那么我们就将这个节点插入到队头去,否则我们还是插入到队尾.
这个就是非常好用的SLF优化算法.
代码解析
#include <bits/stdc++.h>
using namespace std;
const int N=400000 +100;
int head[N],ver[N],Next[N],edge[N],vis[N],dis[N],tot;
void add_edge(int a,int b,int c)
{
edge[tot]=b;
ver[tot]=c;
Next[tot]=head[a];
head[a]=tot++;
}
void spfa(int s)
{
memset(dis,0x3f,sizeof(dis));
memset(vis,false,sizeof(vis));
deque<int> q;
dis[s]=0;
vis[s]=true;
q.push_back(s);
while(q.size())
{
int now=q.front();
vis[now]=false;
q.pop_front();
for(int i=head[now]; ~i; i=Next[i])
{
int j=edge[i];
if (dis[j]>dis[now]+ver[i])
{
dis[j]=dis[now]+ver[i];
if (!vis[j])
{
vis[j]=true;
if (q.size() && dis[j]<dis[q.front()])
q.push_front(j);
else
q.push_back(j);
}
}
}
}
}
int main()
{
int t,r,p,s,x,y,z;
ios::sync_with_stdio(false);
cin.tie(0);
cin>>t>>r>>p>>s;
memset(head,-1,sizeof(head));
for(int i=1; i<=r; i++)
{
cin>>x>>y>>z;
add_edge(x,y,z);
add_edge(y,x,z);
}
for(int i=1; i<=p; i++)
{
cin>>x>>y>>z;
add_edge(x,y,z);
}
spfa(s);
for(int i=1; i<=t; i++)
{
if (dis[i]==0x3f3f3f3f)
cout<<"NO PATH"<<endl;
else
cout<<dis[i]<<endl;
}
return 0;
}
SLF时间复杂度上界是指数级的……那根本不能称之为优化……
orz
突然发现题目限制 Ci 范围只有 10000,所以好像很难被卡
lyd大佬现场卡此代码qwq
佬,所有卡spfa的算法都可以用这个SLF来处理吗
大佬,请问可以解释下SLF的正确性吗,不太理解为啥这样做是对的
确实不对,会被卡
if (q.size() && dis[j]<dis[q.front()]) q.push_front(j); else q.push_back(j);
这段啥意思呀,有没有hxd解释一下QAQ
dis[i] 表示从1号点到i号点的距离
如果从1号点到j这个点的距离小于
从1号点到当前队列对头的这个点的距离的话
就把这个点放前面
否则就放队列的后面
楼主你是南外的?
问一下为什么这一题不能加上LLL优化
这就莽过去了QwQ
lyd是金牌爷,只能仰望
秦淮岸大佬将是金牌爷,也只能仰望
金牌是梦想,但是能否实现,永远是谜。
大佬停课了?
为什么我改到和题解只差几个符号还是过不了
我也是 然后直接cpoy他的代码了
您超越了lyd?(滑稽)
话说您考今年的CSP-S吗?
考
lyd太强了,那是金牌爷,只能仰望
那啥。。优先队列优化SPFA为啥过不了
那个叫做dijskra,他无法处理负环.
堆优化的spfa就是dijskra了吗
是的.
我觉不是这样的吧,dij和spfa本质上是两种算法吧
那如果这样的话堆优化spfa为啥跑不了负边权
因为有堆,所以会不断地跑负边,然后就死循环了。
大佬,负边都是单向的,哪来的不断跑?就算能跑,SLF不也是优先扩展权值小的点啊,也会死循环的
抱歉,我说的应该是dijskra不能处理负环。。。
这道题没有负环
并不是会死循环,而是dijkstra求出来的答案会错
想问下,使用spfa算法的时候,队列里的元素的前后顺序是否对于整个算法有影响?为什么呢?我觉得那个队列无序也可以呀
有的,比如说dijskra
真就来spfa啊(用lyd的做法wa得难受)
SLF非常有趣.(滑稽,逃