Submission #43597

#	Time	Username	Problem	Language	Result	Execution time	Memory
43597		leehosu01	주유소 (KOI16_gas)	C++14	100 / 100	332 ms	58476 KiB

gas

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct A{ll v,l;}tA;
vector<A>E[2501];
queue<A>Q;//v,l은v정점에 L당l가격으로
bool inQ[2502*2501];
ll pc[2501],n,m,NP[2501][2501],mins=1e16;//NP[I][J]::I번에 L당J가격으로 NP[I][J]비용 쓰면서옴
int main()
{
    int i,mil,a,b,c;
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    for(i=1;i<=n;fill(NP[i++],NP[i]+2501,-1))cin>>pc[i];
    for(i=1;i<=m;i++){cin>>a>>b>>c;E[a].push_back({b,c});E[b].push_back({a,c});}
    NP[1][pc[1]]=0;
    Q.push({1,pc[1]});

    while(!Q.empty())
    {
        tA=Q.front();Q.pop();inQ[tA.v*2501+tA.l]=0;
        for(A&I:E[tA.v])
        {
            mil=min(pc[tA.v],tA.l);
            if(NP[I.v][mil]==-1||NP[I.v][mil]>NP[tA.v][tA.l]+mil*I.l)
            {
                NP[I.v][mil]=NP[tA.v][tA.l]+mil*I.l;
                if(!inQ[I.v*2501+mil]){Q.push({I.v,mil});inQ[I.v*2501+mil]=1;}
            }
        }
    }
    for(i=0;i<=2500;i++)if(NP[n][i]!=-1)mins=min(mins,NP[n][i]);
    printf("%lld",mins);
}

Compilation message (stderr)

gas.cpp: In function 'int main()':
gas.cpp:15:44: warning: operation on 'i' may be undefined [-Wsequence-point]
     for(i=1;i<=n;fill(NP[i++],NP[i]+2501,-1))cin>>pc[i];
                                            ^

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