[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;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology