[TIOJ]1561. 改變路線
題目連結:http://tioj.ck.tp.edu.tw/problems/1561
裸次短路徑。
裸次短路徑。
#include <iostream> #include <algorithm> #include <cmath> #include <bitset> #include <queue> #include <vector> #define lld long long #define PB push_back #define F first #define S second #define jizz cin.tie(0);ios_base::sync_with_stdio(0); #define endl '\n' using namespace std; typedef pair<int,int> Pair; struct Ken{ int to,w; }; vector<Ken> v[105]; Pair dis[105]; int main(){jizz int n,m; while(cin >> n >> m){ fill(dis,dis+105,(Pair){1e9,1e9}); for(int i = 0 ; i < 105 ; i++)v[i].clear(); while(m--){ int a,b,c;cin >> a >> b >> c; v[a].PB({b,c}); v[b].PB({a,c}); } int st,ed;cin >> st >> ed; priority_queue<Pair,vector<Pair> , greater<Pair> > pq; pq.push({0,st}); dis[st].F = 0; while(!pq.empty()){ int now = pq.top().S,d = pq.top().F;pq.pop(); for(Ken i : v[now]){ int f1 = d+i.w; if(f1 < dis[i.to].F){ dis[i.to].S = dis[i.to].F; dis[i.to].F = f1; pq.push({dis[i.to].F,i.to}); }else if(f1 > dis[i.to].F && f1 < dis[i.to].S){ dis[i.to].S = f1; pq.push({dis[i.to].S,i.to}); } } } cout << (dis[ed].S == 1e9? -1 : dis[ed].S) << endl; } return 0; }
留言
張貼留言