제출 #81467

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
81467		igzi	Cities (BOI16_cities)	C++17	100 / 100	4148 ms	45244 KiB

cities

#include <bits/stdc++.h>
#define INF 100000000000000000
#define maxN 100002

using namespace std;

long long n,m,k,t,i,j,x,y,z,dp[35][maxN];
vector < pair<long long,long long> > adj[maxN];
vector <long long> v;
bool mar[maxN];


int main()
{
    cin>>n>>k>>m;
    for(i=0;i<k;i++){
        cin>>x;
        x--;
        v.push_back(x);
    }
    for(i=0;i<m;i++){
        cin>>x>>y>>z;
        x--;
        y--;
        adj[x].push_back(make_pair(y,z));
        adj[y].push_back(make_pair(x,z));
    }
    for(i=0;i<32;i++){
        for(j=0;j<n;j++) dp[i][j]=INF;
    }
    for(i=0;i<v.size();i++){
        dp[1<<i][v[i]]=0;
    }
    for(i=0;i<pow(2,k);i++){
        for(j=0;j<n;j++){
            for(t=0;t<min(i,i/2+2);t++){
                dp[i][j]=min(dp[i][j],dp[t][j]+dp[i^t][j]);
            }
        }
        priority_queue <pair<long long,long long>, vector<pair<long long,long long>> , greater<pair<long long,long long>>> pq;
        for(j=0;j<n;j++){
            pq.push({dp[i][j],j});
        }
        memset(mar,false,n+2);
        while(!pq.empty()){
            x=pq.top().second;
            pq.pop();
            if(mar[x]) continue;
            for(j=0;j<adj[x].size();j++){
                if(dp[i][x]+adj[x][j].second<dp[i][adj[x][j].first]){
                    dp[i][adj[x][j].first]=dp[i][x]+adj[x][j].second;
                    pq.push({dp[i][adj[x][j].first],adj[x][j].first});
                }
            }
        }
    }
    long long ans=INF;
    for(i=0;i<n;i++){
        ans=min(ans,dp[(1<<k)-1][i]);
    }
    cout<<ans<<endl;
    return 0;
}

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

cities.cpp: In function 'int main()':
cities.cpp:31:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<v.size();i++){
             ~^~~~~~~~~
cities.cpp:49:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(j=0;j<adj[x].size();j++){
                     ~^~~~~~~~~~~~~~

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