15:I[42907,["401","static/chunks/363642f4-812e50cc3e323d2c.js","213","static/chunks/213-b2337299901a9046.js","152","static/chunks/152-6ad5ee8e457afbb4.js","393","static/chunks/393-460011df65777e34.js","659","static/chunks/app/codes/%5Bid%5D/page-f39212c89e2a3314.js"],"CodeViewer"] 16:T706,#include #include #include #include #include #include #include #define MOD 1000000007 #define ll long long #define sz(x) ((int)(x).size()) #define rep(i, n) for(int i=0; i<(n); i++) #define set0(arr) memset(arr, 0, sizeof(arr)) using namespace std; struct comp { bool operator()(const pair a, const pair b) const { return a.second > b.second; } }; vector dijkstra(vector>> &adj, int src) { // pair in adj: (node index, distance) vector dist(sz(adj), INT_MAX); dist[src] = 0; priority_queue, vector>, comp> pq; pq.emplace(src, 0); while(!pq.empty()) { auto v = pq.top(); // shortest path to v.first is found pq.pop(); //if(dist[v.first] < v.second) continue; for(auto pr: adj[v.first]) { if(v.second + pr.second < dist[pr.first]) { dist[pr.first] = v.second + pr.second; pq.emplace(pr.first, dist[pr.first]); } } } return dist; } int main() { //ios::sync_with_stdio(false);cin.tie(NULL); int N, E; cin >> N >> E; vector>> adj(N); rep(i, E) { int u, v, w; cin >> u >> v >> w; u--, v--; adj[u].emplace_back(v, w); adj[v].emplace_back(u, w); } int A, B; cin >> A >> B; A--, B--; vector dist1 = dijkstra(adj, 0), distA = dijkstra(adj, A), distB = dijkstra(adj, B); bool hasans=false; ll ans = LLONG_MAX; if(distA[B] == INT_MAX) return !(cout << -1); if(dist1[B] != INT_MAX && distA[N-1] != INT_MAX) { hasans = true; ans = min(ans, (ll)dist1[B]+(ll)distB[A]+(ll)distA[N-1]); } if(dist1[A] != INT_MAX && distB[N-1] != INT_MAX) { hasans = true; ans = min(ans, (ll)dist1[A]+(ll)distA[B]+(ll)distB[N-1]); } if(hasans)

코드 #505