Submission #56961

#	Time	Username	Problem	Language	Result	Execution time	Memory
56961		red1108	주유소 (KOI16_gas)	C++17	100 / 100	1589 ms	52884 KiB

gas

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#define P pair<long long int,long long int>
using namespace std;
typedef long long ll;
ll n,m;
ll cost[2510];
bool visit[2510];
ll dis[2510][2510];
vector<ll> graph[2510],dist[2510];
priority_queue<P,vector<P>, greater<P> >pq;
P now;
int main()
{
    ll i, j;
    ll a,b,c;
    scanf("%lld %lld", &n, &m);
    for(i=1;i<=n;i++) scanf("%lld", &cost[i]);
    for(i=1;i<=m;i++)
    {
        scanf("%lld %lld %lld", &a, &b, &c);
        graph[a].push_back(b);
        graph[b].push_back(a);
        dist[a].push_back(c);
        dist[b].push_back(c);
    }
    for(i=1;i<=n;i++)
    {
        while(!pq.empty()) pq.pop();
        fill(visit+1,visit+n+1,0);
        pq.push({0,i});
        while(!pq.empty())
        {
            now=pq.top();
            pq.pop();
            if(visit[now.second]) continue;
            visit[now.second]=1;
            for(int to=0;to<graph[now.second].size();to++)
            {
                if((dis[i][graph[now.second][to]]==0||dis[i][graph[now.second][to]]>now.first+dist[now.second][to])&&graph[now.second][to]!=i)
                {
                    dis[i][graph[now.second][to]]=now.first+dist[now.second][to];
                    pq.push({now.first+dist[now.second][to],graph[now.second][to]});
                }
            }
        }
        for(j=1;j<=n;j++)
        {
            dis[i][j]*=cost[i];
        }
    }
    while(!pq.empty()) pq.pop();
    fill(visit+1,visit+n+1,0);
    pq.push({0,1});
    for(i=2;i<=n;i++)
    {
        pq.push({dis[1][i],i});
    }
    while(!pq.empty())
    {
        now=pq.top();
        pq.pop();
        if(visit[now.second]) continue;
        visit[now.second]=1;
        for(i=2;i<=n;i++)
        {
            if(dis[1][i]>now.first+dis[now.second][i])
            {
                dis[1][i]=now.first+dis[now.second][i];
                pq.push({now.first+dis[now.second][i],(ll)i});
            }
        }
    }

    printf("%lld", dis[1][n]);
}

Compilation message (stderr)

gas.cpp: In function 'int main()':
gas.cpp:40:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int to=0;to<graph[now.second].size();to++)
                          ~~^~~~~~~~~~~~~~~~~~~~~~~~~
gas.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~
gas.cpp:20:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1;i<=n;i++) scanf("%lld", &cost[i]);
                       ~~~~~^~~~~~~~~~~~~~~~~~
gas.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld %lld", &a, &b, &c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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