【先言】：
我去，我怎么也不认为这题需要讲，那既然要讲，那就讲点有用的,我想先放张图片
你正经？我不正经,不用翻了，以前的题解没有
【(description)】 ：
题目传送门
给定两种边，一种是无向边 ， 一种是有向边， 无向边可能有负权值 ，但同时保证无负环 ， 有向边保证为正权值， 求解其中的最短路;
数据给定正常，后两个点卡一般的(spfa)
【(solution)】 ：
这这这…… ， 他要是有个环之类的还有说，这没什么可说的，就跑一个从(S)点出发的(spfa)，就可以搞出正解了，，代码就是下方第一个。 那么恭喜你，得到了88分， 但同时，A不掉，出题的(SB)(神犇)卡了(spfa)，其实这一道题，加一个优队优化就可以卡线过去，自然只是卡线。
那也就说，你们来是来看这道题的一个卡线(SB)做法， 不 ， 既然他让我讲，那就来点有用的，不然，他们讲的题(≧▽≦)/辣么(np),我和一个混子一样。得，考虑(Spfa)的优化
【(optimize)】：
众所周知，(spfa)是有优化的。
1.(SLF)优化 ：
也就是用一个(deque) 双端队列 ， （我看lsp写了，懂得都懂） , 将插入的元素与队头进行比较，如果(dis_{now} < dis_{front()}) ,
那就插入队头，否则就插入队尾 ， 代码见(code2)
原理：因为先扩展最小的点可以尽量使程序尽早的结束
这个算法，能让你，避免陷入求了很多次优解 。
2.(LLL)优化 ：
同样是使用双端队列， 但其中维护的是目前的队列中元素到起点的距离的平均值(k) ， 如果(dis_{now} > k) ,就插入队尾，否则插入队首，可以看一下这个网址
原理： 来源--lhy口中的学姐
:
对每个要出对的元素u，比较dis[u]和队列中dis的平均值，
如果dis[u]更大，那么将它弹出放到队尾，取队首元素在进行重复判断，直至存在dis[x]小于平均值
考虑最后的优化 ：
3.(spfa_{dfs}优化)
为毛有个傻der非要喊讲dfs优化，真的是，
经过和牛爷爷的商讨，放弃了，不xi管了，我写挂了，不会写。
【(Code1)】:
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cstdlib>
#define inf 2147483647
#define int long long
using namespace std ;
const int kmaxn = 1e6 + 10 ;
inline int read() {
int x = 0, f = 1 ;
char ch = getchar() ;
while (!isdigit(ch)) {
if (ch == '-')
f = - 1 ;
ch = getchar() ;
}
while (isdigit(ch)) {
x = x * 10 + ch - '0' ;
ch = getchar() ;
}
return x * f ;
}
int n, m, p, s ;
struct node {
int nxt, v, val ;
} edge[kmaxn << 1] ;
int number, head[kmaxn] ;
void add(int u, int v, int w) {
number ++ ;
edge[number].nxt = head[u] ;
edge[number].v = v ;
edge[number].val = w ;
head[u] = number ;
}
int dis[kmaxn] ;
bool vis[kmaxn] ;
void spfa() {
memset(vis, false, sizeof(vis)) ;
dis[s] = 0 ;
queue<int> q ;
q.push(s) ;
vis[s] = true ;
while (!q.empty()) {
int u = q.front() ;
q.pop() ;
vis[u] = false ;
for (int i = head[u] ; i ; i = edge[i].nxt) {
int v = edge[i].v ;
if (dis[v] > dis[u] + edge[i].val) {
dis[v] = dis[u] + edge[i].val ;
if (!vis[v]) {
q.push(v) ;
vis[v] = true ;
}
}
}
}
}
signed main() {
n = read(), m = read(), p = read(), s = read() ;
for (int i = 1 ; i <= m ; i++) {
int u = read(), v = read(), w = read() ;
add(u, v, w) ;
add(v, u, w) ;
}
for (int i = 1 ; i <= p ; i++) {
int u = read(), v = read(), w = read() ;
add(u, v, w) ;
}
for (int i = 1 ; i <= n ; i++)
dis[i] = inf ;
spfa() ;
for (int i = 1 ; i <= n ; i++) {
if (dis[i] == inf)
printf("NO PATH
") ;
else
printf("%lld
", dis[i]) ;
}
return 0 ;
}
【(Code 2)】:
KnightL (话说，这名字啥意思)