oj.uz

Submission #937101

# Submission time Handle Problem Language Result Execution time Memory
937101 2024-03-03T13:29:52 Z 1075508020060209tc Cities (BOI16_cities) C++14
0 / 100
 854 ms 37860 KB 
#include<bits/stdc++.h>
//#include<bits/extc++.h>
using namespace std;
//using namespace __gnu_pbds;
#define int long long
int n;int K;int m;
int imp[8];
vector<pair<int,int>>e[100005];

void dijkstera(vector<int>ost,vector<int>&dis){
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
for(int i:ost){
    pq.push({dis[i],i});
}
bitset<100005>vis;
while(pq.size()){
    int nw=pq.top().second;
    pq.pop();
    if(vis[nw]){continue;}
    vis[nw]=1;
    for(auto pr:e[nw]){
        int v=pr.first;
        int w=pr.second;
        if(vis[v]){continue;}
        if(dis[v]>dis[nw]+w){
            dis[v]=dis[nw]+w;
            pq.push({dis[v],v});
        }
    }
}
}

vector<int>disa[6];
vector<int>disab[6][6];
void init(){
cin>>n>>K>>m;
for(int i=1;i<=K;i++){
    cin>>imp[i];
    disa[i].resize(n+10,0);
}



for(int i=1;i<=m;i++){
    int a;int b;int c;
    cin>>a>>b>>c;
    e[a].push_back({b,c});
    e[b].push_back({a,c});
}
}


signed main(){
init();
for(int i=1;i<=K;i++){
    for(int j=1;j<=n;j++){
        disa[i][j]=1e16;
    }
    disa[i][imp[i]]=0;
    vector<int>vc={imp[i]};
    dijkstera(vc,disa[i]);
}
for(int i=1;i<=K;i++){
    for(int j=i+1;j<=K;j++){
        //if(i==j){continue;}
        disab[i][j].resize(n+10);
        vector<int>vc;
        for(int v=1;v<=n;v++){
            disab[i][j][v]=disa[i][v]+disa[j][v];
            vc.push_back(v);
        }
        dijkstera(vc,disab[i][j]);
    }
}
int ans=1e18;
ans=disab[1][2][imp[3]];
cout<<ans<<endl;


}

Subtask #1
0 / 22.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 451 ms 31028 KB Output is correct
2 Correct 469 ms 29984 KB Output is correct
3 Correct 205 ms 20380 KB Output is correct
4 Correct 128 ms 15300 KB Output is correct
5 Incorrect 255 ms 28192 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 26.0

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