oj.uz

Submission #745864

# Submission time Handle Problem Language Result Execution time Memory
745864 2023-05-21T08:53:00 Z vjudge1 Cities (BOI16_cities) C++11
29 / 100
 6000 ms 46700 KB 
#include <bits/stdc++.h>

using namespace std;
#define int long long int

int n,m,k;
vector<int> t[100001];
vector<int> w[100001];
vector<int> imp;
int a,b,c;
vector<int> dist[5];

void Dijkstra(int p,vector<int> &q) {
    set<pair<int,int> > s; s.clear();
    s.insert( {0,p} );
    q.assign(n+1,-1);
    int len,to;
    while (s.size()>0) {
        len=(*s.begin()).first;
        to=(*s.begin()).second;
        s.erase(s.begin());
        if (q[to]==-1) {
            q[to]=len;
            for (int i=0;i<t[to].size();i++) {
                s.insert( {len+w[to][i],t[to][i]} );
            }
        }
    }
}

void kiir() {
    for (int i=0;i<k;i++) {
        cout << imp[i] << ": " << endl;
        for (int j=1;j<=n;j++) {
            cout << j << ": " << dist[i][j] << endl;
        }
        cout << endl;
    }
}

vector<int> dis[1001];

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k >> m;
    for (int i=1;i<=k;i++) {
        cin >> a;
        imp.push_back(a);
    }
    for (int i=1;i<=m;i++) {
        cin >> a >> b >> c;
        t[a].push_back(b);
        t[b].push_back(a);
        w[a].push_back(c);
        w[b].push_back(c);
    }
    if (k==2) {
        for (int i=0;i<k;i++) {
            Dijkstra(imp[i],dist[i]);
        }
        cout << dist[0][imp[1]] << endl;
        return(0);
    }
    if (k==3) {
        for (int i=0;i<k;i++) {
            Dijkstra(imp[i],dist[i]);
        }
        int ans=1e18;
        for (int i=1;i<=n;i++) {
            ans=min(ans,dist[0][i]+dist[1][i]+dist[2][i]);
        }
        cout << ans << endl;
        return(0);
    }
    if (k==4) {
        for (int i=1;i<=n;i++) {
            Dijkstra(i,dis[i]);
        }
        int ans=1e18;
        for (int i=1;i<=n;i++) {
            for (int j=1;j<=n;j++) {
                ans=min(ans,dis[imp[0]][i]+dis[imp[1]][i]+dis[i][j]+dis[j][imp[2]]+dis[j][imp[3]]);
                ans=min(ans,dis[imp[0]][i]+dis[imp[2]][i]+dis[i][j]+dis[j][imp[1]]+dis[j][imp[3]]);
                ans=min(ans,dis[imp[0]][i]+dis[imp[3]][i]+dis[i][j]+dis[j][imp[1]]+dis[j][imp[2]]);
            }
        }
        cout << ans << endl;
        return(0);
    }
    return 0;
}

Compilation message

cities.cpp: In function 'void Dijkstra(long long int, std::vector<long long int>&)':
cities.cpp:24:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |             for (int i=0;i<t[to].size();i++) {
      |                          ~^~~~~~~~~~~~~

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5040 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Incorrect 3 ms 5048 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1083 ms 33388 KB Output is correct
2 Correct 1044 ms 34560 KB Output is correct
3 Correct 185 ms 15812 KB Output is correct
4 Correct 1014 ms 41204 KB Output is correct
5 Correct 735 ms 33384 KB Output is correct
6 Correct 704 ms 41288 KB Output is correct
7 Correct 5 ms 5312 KB Output is correct
8 Correct 5 ms 5204 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 708 ms 13168 KB Output is correct
2 Correct 788 ms 13112 KB Output is correct
3 Correct 225 ms 12972 KB Output is correct
4 Correct 394 ms 7220 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6017 ms 46700 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 183 ms 21076 KB Output isn't correct
2 Halted 0 ms 0 KB -