1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m, s, t;
    scanf("%d%d%d%d", &n, &m, &s, &t);
    vector<vector<pair<int,int> > > g(n + 1);
    for(int i=0; i<m; i++) {
        int x, y, w;
        scanf("%d%d%d", &x, &y, &w);
        g[x].push_back(make_pair(y, w));
        g[y].push_back(make_pair(x, w));
    }
    vector<int> dis(n + 1, 0x3f3f3f3f);
    vector<int> tag(n + 1, false);
    dis[s] = 0;
    priority_queue<pair<int,int> > que;
    for(que.push(make_pair(0, s)); !que.empty(); ) {
        int x = que.top().second;
        que.pop();
        if(tag[x]) continue;
        tag[x] = true;
        if(x == t) break;
        for(int i=0; i<g[x].size(); ++i) {
            int y = g[x][i].first;
            int w = g[x][i].second;
            if(dis[y] > dis[x] + w) {
                dis[y] = dis[x] + w;
                que.push(make_pair(-dis[y], y));
            }
        }
    }
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX