제출 #90121

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
90121		Harvey_Rollens	Evacuation plan (IZhO18_plan)	C++17	10 / 100	4091 ms	56148 KiB

plan

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define st string
#define fr first
#define se second

const ll mod=998244353;

using namespace std;

vector<pair<ll, ll> > v[100010];
priority_queue<pair<ll, ll> > q;
ll a[100010], n, m, k, ans=0;
map<ll, ll> dp[100200], us;

void dej(ll xx)
{
    for(ll i=1; i<=n; i++)
        dp[xx][i]=1e10;
    dp[xx][xx]=0;

    q.push({xx, dp[xx][xx]});
    while(!q.empty())
    {
        ll x=q.top().fr, s=q.top().se;
        q.pop();

        if(s>dp[xx][x])
            continue;

        for(ll i=0; i<v[x].size(); i++)
        {
            ll y=v[x][i].fr, p=v[x][i].se;
            if(dp[xx][x]+p<dp[xx][y])
            {
                dp[xx][y]=dp[xx][x]+p;
                q.push({y, dp[xx][y]});
            }
        }
    }
}

void dfs(ll x, ll y, ll mn)
{
    us[x]=1;

    if(x==y)
    {
        ans=max(ans, mn);
        return;
    }

    for(ll i=0; i<v[x].size(); i++)
    {
        ll to=v[x][i].fr;
        if(!us[to])
        {
            ll l=1e10;
            for(ll j=1; j<=k; j++)
                l=min(l, dp[a[j]][to]);

            dfs(to, y, min(mn, l));
        }
    }
}

int main()
{
    //freopen("1.txt", "r", stdin);
    //freopen("1.txt", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>n>>m;

    for(ll i=1; i<=m; i++)
    {
        ll x, y, z;
        cin>>x>>y>>z;
        v[x].push_back({y, z});
        v[y].push_back({x, z});
    }

    cin>>k;

    for(ll i=1; i<=k; i++)
    {
        cin>>a[i];
        dej(a[i]);

        /*for(ll j=1; j<=n; j++)
        {
            cout<<dp[a[i]][j]<<" ";
        }
        cout<<endl;*/
    }

    ll w;
    cin>>w;
    while(w--)
    {
        ll x, y;
        cin>>x>>y;

        //ans=0;
        //dfs(x, y, 1e10);

        //cout<<ans<<endl;
        //us.clear();

        ll l=1e10;
        for(ll j=1; j<=k; j++)
            l=min(l, dp[a[j]][x]);
        for(ll j=1; j<=k; j++)
            l=min(l, dp[a[j]][y]);

            cout<<l<<endl;
    }
    return 0;
}
/*
*/

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

plan.cpp: In function 'void dej(long long int)':
plan.cpp:32:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(ll i=0; i<v[x].size(); i++)
                     ~^~~~~~~~~~~~
plan.cpp: In function 'void dfs(long long int, long long int, long long int)':
plan.cpp:54:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ll i=0; i<v[x].size(); i++)
                 ~^~~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:116:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
         for(ll j=1; j<=k; j++)
         ^~~
plan.cpp:119:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
             cout<<l<<endl;
             ^~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 46