제출 #1069875

#제출 시각아이디문제언어결과실행 시간메모리
1069875Hugo1729Commuter Pass (JOI18_commuter_pass)C++17
0 / 100
198 ms20656 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; int n,m,a,b,c,d; vector<pair<ll,int>> adj[100001]; vector<ll> dijkstra(int start){ vector<ll> dist(n+1, LLONG_MAX); // Dijkstra's algorithm using T = pair<long long, int>; priority_queue<T, vector<T>, greater<T>> pq; dist[start] = 0; // The shortest path from a node to itself is 0 pq.push({0, start}); while (!pq.empty()) { const auto [cdist, node] = pq.top(); pq.pop(); if (cdist != dist[node]) { continue; } for (const pair<ll, int> &i : adj[node]) { // If we can reach a neighbouring node faster, // we update its minimum distance if (cdist + i.first < dist[i.second]) { pq.push({dist[i.second] = cdist + i.first, i.second}); } } } return dist; } int main(){ cin.tie(0)->sync_with_stdio(0); cin >> n >> m >> a >> b >> c >> d; for(int i=0;i<m;i++){ int x,y,cost; cin >> x >> y >> cost; adj[x].push_back({cost,y}); adj[y].push_back({cost,x}); } vector<ll> path1 = dijkstra(a),path2 = dijkstra(b),sus1=dijkstra(c),sus2=dijkstra(d); vector<ll> dp(n+1,LLONG_MAX/4),dp1(n+1,LLONG_MAX/4),dp2(n+1,LLONG_MAX/4); // vector<pair<ll,ll>> dp1(n+1,{LLONG_MAX,LLONG_MAX}),dp2(n+1,{LLONG_MAX,LLONG_MAX}); vector<pair<ll,int>> elza; for(int i=1;i<=n;i++){ if(path1[i]+path2[i]==path1[b])elza.push_back({path1[i],i}); } dp[a]=sus1[a]+sus2[a]; dp1[a]=sus1[a]; dp2[a]=sus2[a]; sort(elza.begin(),elza.end()); for(int i=0;i<elza.size();i++){ int v = elza[i].second; for(auto [cost, w] : adj[v]){ if(path1[v]+path2[v]==path1[b]&&path1[w]<path1[v]){ dp1[v]=min(dp1[w],sus1[v]); dp2[v]=min(dp2[w],sus2[v]); dp[v]=min(dp[v],dp[w]); } } for(auto [cost, w] : adj[v]){ if(path1[v]+path2[v]==path1[b]&&path1[w]<path1[v]){ dp[v]=min(dp[v],dp1[v]+sus2[v]); dp[v]=min(dp[v],dp2[v]+sus1[v]); } } cout << v <<' ' << path1[v] << ": " << dp[v] << ' ' << dp1[v] << ' ' << dp2[v] << '\n'; } cout << min(dp[b],sus1[d]); // cout << '\n'; // for(int i = 0;i<elza.size();i++)cout << elza[i].first << ' ' << elza[i].second << '\n'; // cout << '\n'; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:65:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(int i=0;i<elza.size();i++){
      |                 ~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...