제출 #1069897

#제출 시각아이디문제언어결과실행 시간메모리
1069897Hugo1729Commuter Pass (JOI18_commuter_pass)C++17
16 / 100
320 ms21684 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; vector<pair<ll,ll>> adj[100001]; ll n, m; vector<ll> dijkstra(ll start){ vector<ll> dist(n+1, LLONG_MAX); // Dijkstra's algorithm using T = pair<long long, ll>; 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, ll> &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; } ll solve(ll a, ll b, ll c, ll d){ 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,ll>> elza; for(ll 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(ll i=0;i<elza.size();i++){ ll 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'; } return min(dp[b],sus1[d]); } int main(){ cin.tie(0)->sync_with_stdio(0); ll a,b,c,d; cin >> n >> m >> a >> b >> c >> d; for(ll i=0;i<m;i++){ ll x,y,cost; cin >> x >> y >> cost; adj[x].push_back({cost,y}); adj[y].push_back({cost,x}); } cout << min(solve(a,b,c,d),solve(b,a,c,d)); // cout << '\n'; // for(ll i = 0;i<elza.size();i++)cout << elza[i].first << ' ' << elza[i].second << '\n'; // cout << '\n'; return 0; }

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

commuter_pass.cpp: In function 'll solve(ll, ll, ll, ll)':
commuter_pass.cpp:53:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(ll 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...