Untitled

mail@pastecode.io avatar
unknown
plain_text
16 days ago
1.0 kB
4
Indexable
Never
#include <vector>
#include <iostream>
#include <queue>
#include <climits>

#define pb push_back

using namespace std;
typedef long long ll;

typedef pair<int, int> pii;

const int maxn = 100001;

int n, m, s, t, x, y, z;
vector<pii> adj[maxn];
ll d[maxn];

void dijkstra(int s, int t){
    for(int i = 1; i <= n; i++) d[i] = LLONG_MAX;
    d[s] = 0;
    
    priority_queue<pii, vector<pii>, greater<pii>> Q;
    Q.push({0, s});
    while(!Q.empty()){
        pii top = Q.top(); Q.pop();
        int u = top.second, len = top.first;
        if(len > d[u]) continue;
        for(pii p : adj[u]){
            int v = p.first, w = p.second;
            if(d[v] > d[u] + w){
                d[v] = d[u] + w;
                Q.push({d[v], v});
            }
        }
    }
    cout << d[t];
}

int main() {
    cin >> n >> m >> s >> t;
    for(int i = 0; i < m; i++){
        cin >> x >> y >> z;
        adj[x].pb({y, z});
        adj[y].pb({x, z});
    }
    adj[t].clear();
    dijkstra(s, t);
    
    return 0;
}








Leave a Comment