제출 #745956

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
745956		vjudge1	Cities (BOI16_cities)	C++11	51 / 100	6094 ms	53380 KiB

cities

#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;

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

void Dijkstra(int p,vector<ll> &q) {
    set<pair<ll,int> > s; s.clear();
    s.insert( {ll(0),p} );
    q.assign(n+1,-1);
    ll len;
    int 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<ll> dis[1001];

void Dijkstra2(int p,vector<ll> &q) {
    set<pair<ll,int> > s; s.clear();
    s.insert( {0,p} );
    q.assign(n+3,-1);
    ll len;
    int 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]} );
            }
        }
    }
}

int 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]);
        }
        ll 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) && (n<=1000)) {
        for (int i=1;i<=n;i++) {
            Dijkstra(i,dis[i]);
        }
        ll 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);
    }

    if (k==4) {
        ll ans=1e18;
        for (int i=0;i<k;i++) {
            Dijkstra(imp[i],dist[i]);
        }
        //kiir();
        vector<ll> r;
        for (int i=1;i<=n;i++) {
            t[n+1].push_back(i);
            w[n+1].push_back(dist[0][i]+dist[1][i]);
            t[i].push_back(n+1);
            w[i].push_back(dist[0][i]+dist[1][i]);
        }
        for (int i=1;i<=n;i++) {
            t[n+2].push_back(i);
            w[n+2].push_back(dist[2][i]+dist[3][i]);
            t[i].push_back(n+2);
            w[i].push_back(dist[2][i]+dist[3][i]);
        }
        Dijkstra2(n+1,r);
        ans=min(ans,r[n+2]);

        for (int i=1;i<=n;i++) {
            w[i].pop_back();
            w[i].pop_back();
            w[n+1][i-1]=dist[0][i]+dist[2][i];
            w[i].push_back(dist[0][i]+dist[2][i]);
        }
        for (int i=1;i<=n;i++) {
            w[n+2][i-1]=dist[1][i]+dist[3][i];
            w[i].push_back(dist[1][i]+dist[3][i]);
        }
        Dijkstra2(n+1,r);
        ans=min(ans,r[n+2]);


        for (int i=1;i<=n;i++) {
            w[i].pop_back();
            w[i].pop_back();
            w[n+1][i-1]=dist[0][i]+dist[3][i];
            w[i].push_back(dist[0][i]+dist[3][i]);
        }
        for (int i=1;i<=n;i++) {
            w[n+2][i-1]=dist[2][i]+dist[1][i];
            w[i].push_back(dist[2][i]+dist[1][i]);
        }
        Dijkstra2(n+1,r);
        ans=min(ans,r[n+2]);

        cout << ans << endl;
        return(0);

    }
    if (k==5) {
        for (int i=1;i<=n;i++) {
            Dijkstra(i,dis[i]);
        }
        ll ans=1e18;
        vector<int> a; a=imp;
        for (int i=0;i<120;i++) {
            for (int i=1;i<=n;i++) {
                for (int j=1;j<=n;j++) {
                    for (int l=1;l<=n;l++) {
                        ans=min(ans,dis[a[0]][i]+dis[a[1]][i]+dis[a[2]][j]+dis[a[3]][j]+dis[a[4]][l]+dis[i][l]+dis[j][l]);
                    }
                }
            }
            next_permutation(a.begin(),a.end());
        }
        cout << ans << endl;
    }
    return 0;
}

/*
8 5 12
1 3 4 7 2
1 2 1
2 3 1
3 4 20
4 5 6
5 6 9
6 7 11
7 8 10
1 8 4
8 4 5
2 7 8
3 6 3
5 7 6
*/

컴파일 시 표준 에러 (stderr) 메시지

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

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