Submission #40093

#	Time	Username	Problem	Language	Result	Execution time	Memory
40093		igzi	Cities (BOI16_cities)	C++14	0 / 100	966 ms	33236 KiB

cities

#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> > 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));
            }
    }
}
}

pair <long long,long long> resi(vector <long long> v,vector <long long> u){
long long i,j,a,b,x,m=LLONG_MAX;
for(i=0;i<v.size();i++){
    dijkstra(v[i],i);
}
for(i=0;i<v.size();i++){
    for(j=0;j<u.size();j++){
        if(d[i][u[j]]<m){
            a=i;
            b=u[j];
            m=d[i][u[j]];
        }
    }
}
x=b;
while(par[a][x].first!=-1){
    adj[par[a][x].first][par[a][x].second].second=0;
    x=par[a][x].first;
}
return make_pair(b,m);
}

int main()
{
    long long t=0;
    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));
    }
    u.push_back(v[0]);
    v.erase(v.begin());
    while(v.size()){
        pair <long long,long long> p;
        p=resi(u,v);
        t+=p.second;
        u.push_back(p.first);
        for(i=0;i<v.size();i++){
            if(v[i]==p.first){
                v.erase(v.begin()+i);
                break;
            }
        }
    }
    cout<<t<<endl;
    return 0;
}

Compilation message (stderr)

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++){
                  ^
cities.cpp: In function 'std::pair<long long int, long long int> resi(std::vector<long long int>, std::vector<long long int>)':
cities.cpp:38:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<v.size();i++){
          ^
cities.cpp:41:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<v.size();i++){
          ^
cities.cpp:42:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(j=0;j<u.size();j++){
              ^
cities.cpp: In function 'int main()':
cities.cpp:78:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=0;i<v.size();i++){
                  ^
cities.cpp: In function 'std::pair<long long int, long long int> resi(std::vector<long long int>, std::vector<long long int>)':
cities.cpp:51:17: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]
 while(par[a][x].first!=-1){
                 ^
cities.cpp:51:17: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]

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