Submission #1135281

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135281		rlx0090	약속장소 정하기 (GCJ12KOR_appointment)	C++20	35 / 35	365 ms	5568 KiB

C

#include <iostream>
#include <vector>
#include <fstream>
#include <cstring>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <cfloat>
#include <random>
#include <complex>
#include<assert.h>

using namespace std;
long long inf = 1e18;
void dijkstra(int s, int t, int wei, vector<vector<pair<int, int> > > & adj, vector<long long> & dist, vector<int> & cnt) {
    //cout << "start : " << s << endl;
    vector<long long> d(t + 1, inf);
    priority_queue<pair<int, int> > pq;
    d[s] = 0;
    pq.push({0, s});
    while(!pq.empty()) {
        pair<int, int> f = pq.top(); pq.pop();
        int here = f.second;
        int dist2here = -f.first;
        if(dist2here > d[here]) continue;
        for(int i = 0; i < adj[here].size(); ++i) {
            int there = adj[here][i].first;
            int dist2there = adj[here][i].second * wei;
            // cout << "there : " << there;
            // cout << " dist there : " << d[there] << " cand : " << dist2here + dist2there << endl;
            if(d[there] > dist2here + dist2there) {
                d[there] = dist2here + dist2there;
                pq.push({-d[there], there});
            }
        }
    }
    
    for(int i = 1; i < t; ++i) {
        //cout << "i : " << i << " d : " << d[i] << endl;
        if(d[i] < inf) {
            cnt[i]++;
            dist[i] = max(dist[i], d[i]);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    int CASE = 1;
    while(t--) {
        int n, p, m;
        cin >> n >> p >> m;
        vector<pair<int, int> > h;
        for(int i = 0; i < p; ++i) {
            int x, v;
            cin >> x >> v;
            h.push_back({x, v});
        }
        vector<vector<pair<int, int> > > adj(n + 2);
        
        for(int i = 1; i <= n; ++i)
            adj[i].push_back({n + 1, 0});
        
        for(int i = 0; i < m; ++i) {
            int d, l;
            cin >> d >> l;
            assert(l >= 2);
            int f;
            cin >> f;
            for(int j = 1; j < l; ++j) {
                int c;
                cin >> c;
                //cout << "c : " << c << " f : " << f << endl; 
                adj[f].push_back({c, d});
                adj[c].push_back({f, d});
                f = c;
            }
        }
        
        vector<long long> dist(n + 2);
        vector<int> cnt(n + 2);
        for(int i = 0; i < p; ++i)
            dijkstra(h[i].first, n + 1, h[i].second, adj, dist, cnt);
        
        int chk = 0;
        long long ans = inf;
        for(int i = 1; i <= n; ++i) {
            //cout << "cnt : " << cnt[i] << endl;
            if(cnt[i] == p) {
                ans = min(ans, dist[i]);
                chk = 1;
            }
        }
            
                
        if(!chk) ans = -1;
        
        cout << "Case #" << CASE++ <<": " << ans << '\n';
    }
} 

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25