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