[TIOJ] 1561. 改變路線

題目連結:http://tioj.infor.org/problems/1561

---

原來本題是嚴格次短路徑= =
寫個奇怪的SPFA，除了算最短路徑以外也同時算個次短路徑，而要算最短路徑就枚舉一下當前拿來鬆弛他人的點的第一或第二短路徑，看看他可不可以讓原本的次短更短，但同時也不能比原本的短

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
typedef pair<int,int> PII;
#define FF first
#define SS second
const int INF = 1<<29;
const int N = 100 + 5;

vector<PII> G[N];
PII dis[N];
bitset<N> inq;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n, m;
	while(cin>>n>>m){
		for(int i=0;i<n;i++) G[i].clear();
		fill(dis, dis+n, (PII){INF, INF});
		inq.reset();
		for(int i=0;i<m;i++){
			int u, v, c; cin>>u>>v>>c;
			G[u].PB({v, c});
			G[v].PB({u, c});
		}
		int st, ed; cin>>st>>ed;
		dis[st].FF=0;
		queue<int> SPFA;
		inq[st]=1; SPFA.push(st);
		while(!SPFA.empty()){
			int u = SPFA.front(); SPFA.pop();
			inq[u]=0;
			for(auto i: G[u]){
				int v = i.FF, c = i.SS;
				if(dis[v].FF > dis[u].FF+c){
					dis[v].SS = dis[v].FF;
					dis[v].FF = dis[u].FF+c;
					if(!inq[v]){
						SPFA.push(v);
						inq[v]=1;
					}
				}
				if(dis[v].SS > dis[u].FF+c and dis[u].FF+c > dis[v].FF){
					dis[v].SS = dis[u].FF+c;
					if(!inq[v]){
						SPFA.push(v);
						inq[v]=1;
					}
				}
				if(dis[v].SS > dis[u].SS+c and dis[u].SS+c > dis[v].FF){
					dis[v].SS = dis[u].SS+c;
					if(!inq[v]){
						SPFA.push(v);
						inq[v]=1;
					}
				}
			}
		}
		if(dis[ed].SS == INF) cout<<-1<<'\n';
		else cout<<dis[ed].SS<<'\n';
	}
	return 0;
}