oj.uz

Submission #81466

# Submission time Handle Problem Language Result Execution time Memory
81466 2018-10-24T18:46:20 Z igzi Cities (BOI16_cities) C++17
14 / 100
 696 ms 33516 KB 
#include <bits/stdc++.h>
#define maxN 100002
 
using namespace std;
 
vector < pair<long long,long long> > adj[maxN];
vector <long long> v,u;
long long n,m,k,i,x,y,z,d[7][maxN];
pair <long long,long long> par[7][maxN];
 
void dijkstra(int n,int x){
priority_queue < pair<long long,long long>, vector< pair<long long,long long> > , greater< pair<long long,long long> > > pq;
bool mar[maxN];
pq.push(make_pair(0,n));
for(int i=0;i<maxN;i++){
    mar[i]=false;
    d[x][i]=LLONG_MAX;
}
d[x][n]=0;
par[x][n]=make_pair(-1,-1);
while(!pq.empty()){
    long long c=pq.top().second;
    pq.pop();
    if(mar[c]) continue;
    mar[c]=true;
    for(int i=0;i<adj[c].size();i++){
        if(d[x][adj[c][i].first]>d[x][c]+adj[c][i].second){
            d[x][adj[c][i].first]=d[x][c]+adj[c][i].second;
            par[x][adj[c][i].first]=make_pair(c,i);
            pq.push(make_pair(d[x][adj[c][i].first],adj[c][i].first));
            }
    }
}
}
 
int main()
{
    long long t=LLONG_MAX;
    cin>>n>>k>>m;
    for(i=0;i<k;i++){
        cin>>x;
        v.push_back(x);
    }
    for(i=0;i<m;i++){
        cin>>x>>y>>z;
        adj[x].push_back(make_pair(y,z));
        adj[y].push_back(make_pair(x,z));
    }
    for(i=0;i<k;i++) dijkstra(v[i],i);
    if(k==2) {cout<<d[0][v[1]]<<endl; return 0;}
    for(i=0;i<n;i++) t=min(t,d[0][i]+d[1][i]+d[2][i]);
    cout<<t<<endl;
    return 0;
}

Compilation message

cities.cpp: In function 'void dijkstra(int, int)':
cities.cpp:26:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<adj[c].size();i++){
                 ~^~~~~~~~~~~~~~

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4344 KB Output is correct
2 Correct 5 ms 4524 KB Output is correct
3 Correct 6 ms 5160 KB Output is correct
4 Incorrect 7 ms 6108 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 530 ms 26564 KB Output is correct
2 Correct 519 ms 29292 KB Output is correct
3 Correct 238 ms 29292 KB Output is correct
4 Correct 244 ms 29292 KB Output is correct
5 Correct 466 ms 29292 KB Output is correct
6 Correct 242 ms 29292 KB Output is correct
7 Correct 10 ms 29292 KB Output is correct
8 Correct 10 ms 29292 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 26.0

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