Copy Copied! Back
#include <bits/stdc++.h> #define ALL(A) (A).begin(),(A).end() #define ll long long #define rep(i,n) for(int i=0;i<(n);i++) #define P pair<ll,ll> const ll mod = 1e9+7; const ll INF = -1*((1LL<<63)+1); const int inf = -1*((1<<31)+1); using namespace std; struct edge{ int to; int yen; int snuke; }; void dijkstra(int s,vector<vector<edge>> &g,vector<ll> &y_cost,vector<ll> &s_cost,int x){ priority_queue<P,vector<P>,greater<P>> q; q.push(P(0,s)); if(x==0){ //sから開始してiまで行くのにかかる最小円を求める fill(ALL(y_cost),1e16); y_cost[s] = 0; while(!q.empty()){ P now = q.top();q.pop(); ll cost = now.first; ll nowv = now.second; for(int i=0;i<g[nowv].size();i++){ edge nextedge = g[nowv][i]; if(y_cost[nextedge.to]>y_cost[nowv]+nextedge.yen){ y_cost[nextedge.to] = y_cost[nowv]+nextedge.yen; q.push(P(y_cost[nowv]+nextedge.yen,nextedge.to)); } } } }else{ //sから開始してiまで行くのにかかる最小スクークを求める fill(ALL(s_cost),1e16); s_cost[s] = 0; while(!q.empty()){ P now = q.top();q.pop(); ll cost = now.first; ll nowv = now.second; for(int i=0;i<g[nowv].size();i++){ edge nextedge = g[nowv][i]; if(s_cost[nextedge.to]>s_cost[nowv]+nextedge.snuke){ s_cost[nextedge.to] = s_cost[nowv]+nextedge.snuke; q.push(P(y_cost[nowv]+nextedge.snuke,nextedge.to)); } } } } } int main(void){ cin.tie(0); ios::sync_with_stdio(false); int n,m,s,t; cin >> n >> m >> s >> t; vector<vector<edge>> g(n); vector<ll> y_cost(n),s_cost(n); //y_cost[i] := sからiまで行くのにかかる最小円 //s_cost[i] := tからiまで行くのにかかる最小スヌーク rep(i,m){ int u,v,a,b; cin >> u >> v >> a >> b; u--;v--; g[u].push_back({v,a,b}); g[v].push_back({u,a,b}); } dijkstra(s,g,y_cost,s_cost,0); dijkstra(t,g,y_cost,s_cost,1); //y_cost[i] := sからiまで行くのにかかる最小円 //s_cost[i] := tからiまで行くのにかかる最小スヌーク }