Submission #3856125

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <list>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <string>
#include <bitset>
#include <fstream>
#include <iomanip>

using namespace std;

typedef long long ll;
typedef long double db;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
typedef vector<pii> vii;

#define INF 10000000000000007ll
#define pb push_back
#define mp make_pair
#define err(x) cout<<#x<<"= "<<x<<endl;
#define rep(i,n) for(int i =0; i< n; i++)
#define ff first
#define ss second
#define cil(a,b) ( ((a)%(b) == 0)?((a)/(b)):((a)/(b)+1) )
#define SIZE 100010
#define eps 1e-13
set<pll > llist[SIZE];
int n,m,s,t;

ll dist[SIZE],dis2[SIZE],nxt[SIZE];
priority_queue<pll, vector<pll >, greater<pll > > pq;

int main(){
//	#ifdef ONLINE_JUDGE
//	freopen("little.in", "r" , stdin);
//	freopen("little.out", "w", stdout);
// cin.tie(false); cout.tie(false);	
//	#endif
	ios::sync_with_stdio(false);
	cin>>n>>m>>s>>t;s--;t--;
	rep(i,m){
		ll a,b,c;
		cin>>a>>b>>c;a--;b--;
		llist[a].insert(mp(b,c));
		llist[b].insert(mp(a,c));
	}
	rep(i,n) dist[i]= dis2[i] = INF,nxt[i] =-1;
	
	pq.push(mp(0,t));dist[t] = 0;dis2[t] = 0;
	while(!pq.empty()){
		pll top = pq.top();pq.pop();
		if(dist[top.ss] !=top.ff && dis2[top.ss] != top.ff) continue;
//		cout<<endl;	
	//	cout<<top.ss << "is fixed at dist of "<<top.ff<<endl;
		for( pll x: llist[top.ss]){
			if(dist[x.ff] > top.ff + x.ss ){
				swap(dist[x.ff], dis2[x.ff]);
				dist[x.ff] = top.ff + x.ss;
				pq.push(mp(dist[x.ff], x.ff));
				nxt[x.ff] = top.ss;
			}
			else if(dis2[x.ff] > top.ff + x.ss&& nxt[top.ss] != x.ff){
				dis2[x.ff] = top.ff+ x.ss;
				pq.push(mp(dis2[x.ff], x.ff));
	//			cout<<x.ff<<" is fixing2 at "<<top.ff + x.ss<<endl;
			}
			else if(dis2[x.ff] > dis2[top.ss] + x.ss && nxt[top.ss] == x.ff){
				dis2[x.ff] = dis2[top.ss] + x.ss;
				pq.push(mp(dis2[x.ff],x.ff));
			
	//			cout<<x.ff<<" is fixing2 at "<<dis2[x.ff]<<endl;
			}
		}
	}	
//	rep(i,n)cout<<dist[i]<<' '<<dis2[i]<<endl;
	ll ans = dis2[s],now= s;
	if(ans == INF){
		cout<<-1<<endl;
		return 0;
	}
	while(now!=t){
		ll nxt =-1,cur = INF;
		for(pll x: llist[now])
			if(cur> dis2[x.ff] + x.ss)
				cur = dis2[x.ff] +x.ss,nxt = x.ff;
		now = nxt;
		ans = max(ans , cur);
	}
	cout<<ans<<endl;
	return 0;
};

Submission Info

Judge Result