Submission #746062

#	Time	Username	Problem	Language	Result	Execution time	Memory
746062		vjudge1	Cities (BOI16_cities)	C++14	14 / 100	295 ms	18804 KiB

cities

#include <bits/stdc++.h>

using namespace std;
#define int long long

signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, k, m;
    cin >> n >> k >> m;

    vector<vector<pair<int, int> > > graph(n);
    vector<int> important(k);

    for (int & x : important) cin >> x, x--;

    for (int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;

        a--, b--;
        graph[a].push_back(make_pair(c, b));
        graph[b].push_back(make_pair(c, a));
    }

    // cout << important.size() << endl;
    // for (int x : important) cout << x << " ";
    // cout << endl;

    // cout << 1 << endl;
    long long tenyMo = LONG_LONG_MAX;

    vector<vector<int> > minDists;

    for (int i = 0; i < k; i++){
        int start = important[i];
        vector<int> minDist(n, LONG_LONG_MAX);
        minDist[start] = 0;
        vector<bool> vis(n, false);

        priority_queue<pair<int, int> > q;
        q.push(make_pair(0, start));
        while (!q.empty()){
            int pos = q.top().second, val = -q.top().first;
            q.pop();
            if (vis[pos]) continue;
            vis[pos] = true;
            for (pair<int, int> x : graph[pos]){
                if (vis[x.second] == false && minDist[x.second] > x.first+minDist[pos]){
                    minDist[x.second] = x.first+minDist[pos];
                    q.push(make_pair(-minDist[x.second], x.second));
                }
            }
        }
        minDists.push_back(minDist);
    }
    // cout << 1 << endl;

    // for (auto x : minDists){
    //     for (int y : x){
    //         cout << y << " ";
    //     }
    //     cout << endl;
    // }

    long long mo = LONG_LONG_MAX;
    for (int i = 0; i < n; i++){
        
        long long cnt = 0;
        for (int j = 0; j < k; j++){
            cnt += minDists[j][i];
        }
            
        mo = min(mo, cnt);
    }

    cout << mo << endl;

    return 0;
}

/*

6 3 6
1 2 3
1 2 3
1 3 3
1 4 2
2 3 3 
2 4 2
3 4 2

4 2 5
1 3
1 2 2
1 4 5
2 3 3
2 4 1
3 4 1


*/

Compilation message (stderr)

cities.cpp: In function 'int main()':
cities.cpp:47:39: warning: unused variable 'val' [-Wunused-variable]
   47 |             int pos = q.top().second, val = -q.top().first;
      |                                       ^~~
cities.cpp:34:15: warning: unused variable 'tenyMo' [-Wunused-variable]
   34 |     long long tenyMo = LONG_LONG_MAX;
      |               ^~~~~~

• Subtask 1: 0 / 22
• Subtask 2: 14 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 26