Submission #58657

#	Time	Username	Problem	Language	Result	Execution time	Memory
58657		andy627	주유소 (KOI16_gas)	C++17	100 / 100	915 ms	2916 KiB

gas

#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>
#define LL long long
#define pii pair<int,int>
#define pli pair<LL,int>
#define ff first
#define ss second
#define INF (LL)1e18
using namespace std;

int n,m;
pii oil[2555];
vector<pii> edge[2555];

LL dist[2555],ans[2555];
bool is_gone[2555];

priority_queue<pli,vector<pli>,greater<pli> > pq;

void dijkstra(int idx){
    for(int i=1;i<=n;i++) is_gone[i]=0;
    for(int i=1;i<=n;i++) dist[i]=INF;
    dist[oil[idx].ss]=0;

    is_gone[oil[idx].ss]=1; pq.push({0,oil[idx].ss});
    while(!pq.empty()){
        int v=pq.top().ss; pq.pop();

        for(int i=0;i<edge[v].size();i++){
            if(dist[edge[v][i].ff]>dist[v]+edge[v][i].ss){
                dist[edge[v][i].ff]=dist[v]+edge[v][i].ss;
                is_gone[edge[v][i].ff]=1;
                pq.push({dist[edge[v][i].ff],edge[v][i].ff});
            }
        }
    }
}

int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&oil[i].ff);
        oil[i].ss=i;
    }
    sort(oil+1,oil+n+1);

    while(m--){
        int a,b,w;
        scanf("%d %d %d",&a,&b,&w);
        edge[a].push_back({b,w});
        edge[b].push_back({a,w});
    }

    for(int i=1;i<=n;i++) ans[i]=INF;
    ans[1]=0;

    bool st=0;
    for(int i=n;i>=1;i--){
        if(oil[i].ss==1) st=1;
        if(!st) continue;

        dijkstra(i);

        for(int j=1;j<=n;j++){
            if(j==oil[i].ss) continue;
            ans[j]=min(ans[j],ans[oil[i].ss]+oil[i].ff*dist[j]);
        }
    }

    printf("%lld",ans[n]);

    return 0;
}

Compilation message (stderr)

gas.cpp: In function 'void dijkstra(int)':
gas.cpp:31:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<edge[v].size();i++){
                     ~^~~~~~~~~~~~~~~
gas.cpp: In function 'int main()':
gas.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~~
gas.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&oil[i].ff);
         ~~~~~^~~~~~~~~~~~~~~~~
gas.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d",&a,&b,&w);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 18 / 18
• Subtask 2: 15 / 15
• Subtask 3: 16 / 16
• Subtask 4: 24 / 24
• Subtask 5: 27 / 27