农夫约翰正在一个新的销售区域对他的牛奶销售方案进行调查。
他想把牛奶送到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)O(nlogn)级别的,所以说,我们的算法初步确定在dijskra和SPFA上面.
但是我们发现这道题目一个关键点,就是题目中出现了负权边.
一旦出现了负权边,那么我们只能使用SPFA.lyd大佬的算法过于复杂,我们还是来点容易的水水过去吧
但是对于USACO的题目而言,我们发现他们居然恶心地卡SPFA算法,那么我们不得不使用一些玄学优化.
对于SPFA算法而言,它的优化有两种,我们今天使用SLF优化算法.
众所周知,SPFA算法是一种鉴于队列的实现算法.每一次有节点加入队列都是加入队尾.
但是SLF优化,不同于一般的SPFA算法,它是一种利用双端队列算法处理的问题.
如果说当前点所花费的值少于我们当前队头点的值的话,那么我们就将这个节点插入到队头去,否则我们还是插入到队尾.
这个就是非常好用的SLF优化算法.
**
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int M = 4e5 + 10 ;
const int INF = 0x3f3f3f3f ;
int n , m ;
int e[M] , h[M] , ne[M] , w[M] , idx , dis[M] ;
bool st[M] ;
void add(int a , int b , int c)
{
e[idx] = b , ne[idx] = h[a] , w[idx] = c , h[a] = idx ++ ;
}
void spfa(int s)
{
deque<int> q ;
memset(dis ,0x3f , sizeof dis) ;
q.push_back(s) ;
dis[s] = 0 ;
st[s] = true ;
while(q.size())
{
int u = q.front() ;
q.pop_front() ;
st[u] = false ;
for(int i = h[u] ;i != -1 ;i = ne[i])
{
int j = e[i] ;
if(dis[j] > dis[u] + w[i])
{
dis[j] = dis[u] + w[i] ;
if(!st[j])
{
st[j] = 1 ;
if(q.size() && dis[j] < dis[q.front()])
q.push_front(j) ;
else q.push_back(j) ;
}
}
}
}
return ;
}
int main()
{
int T , R , P , S ;
memset(h , -1 , sizeof h) ;
scanf("%d%d%d%d" , &T , &R , &P , &S) ;
while(R --)
{
int a , b , c ;
scanf("%d%d%d" , &a , &b , &c) ;
add(a , b , c) , add(b , a , c) ;
}
while(P --)
{
int a , b , c ;
scanf("%d%d%d" , &a , &b , &c) ;
add(a , b , c) ;
}
spfa(S) ;
for(int i = 1 ;i <= T ;i ++)
{
if(dis[i] == INF) puts("NO PATH") ;
else printf("%d
" , dis[i]) ;
}
return 0 ;
}