最短路与松弛

#include <bits/stdc++.h>
using namespace std;

int main() {
vector<vector<pair<int,int>>>g(3);g[0]={{1,4},{2,1}};g[2]={{1,2}};
vector<int>d(3,1000000);d[0]=0;priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;q.push({0,0});
while(!q.empty()){auto [dist,u]=q.top();q.pop();if(dist!=d[u])continue;for(auto [v,w]:g[u])if(d[v]>dist+w){d[v]=dist+w;q.push({d[v],v});}}
cout<<d[1]<<" "<<d[2];
}

#include <bits/stdc++.h>
using namespace std;

int main() {
vector<vector<pair<int,int>>>g(3);g[0]={{1,4},{2,1}};g[2]={{1,2}};
vector<int>d(3,1000000);d[0]=0;priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;q.push({0,0});
while(!q.empty()){auto [dist,u]=q.top();q.pop();if(dist!=d[u])continue;for(auto [v,w]:g[u])if(d[v]>dist+w){d[v]=dist+w;q.push({d[v],v});}}
cout<<d[1]<<" "<<d[2];
}