Untitled
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