Submission #1222500

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222500		MarwenElarbi	Wild Boar (JOI18_wild_boar)	C++20	47 / 100	2556 ms	414172 KiB

wild_boar

#include <bits/stdc++.h>
using namespace std;
//common
#define pb push_back
#define se second
#define fi first
#define ll long long 
const int nax=505;
int n,m,t,l;
vector<pair<int,int>> adj[nax];
int to[nax][nax];
pair<int,int> from[nax*2];
long long dst[nax*2][nax*2];
long long dp[100005][505];
int tab[100005];
void djikastra(int i){
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
    pq.push({0,i});
    dst[i][i]=0;
    while(!pq.empty()){
        long long d=pq.top().fi;
        int x=pq.top().se;
        //cout <<from[i].fi<<" "<<from[i].se<<" "<<d<<" "<<from[x].fi<<" "<<from[x].se<<endl;
        pq.pop();
        if(dst[i][x]<d) continue;
        for(auto u:adj[from[x].se]){
            int a=from[x].fi;
            int b=from[x].se;
            if(u.fi==a||u.fi==0) continue;
            long long cur=u.se+d;
            if(cur>=dst[i][to[from[x].se][u.fi]]) continue;
            dst[i][to[from[x].se][u.fi]]=cur;
            pq.push({cur,to[from[x].se][u.fi]});
        }
    }
    return;
}
long long dfs(int i,int lst){
    if(i==l-1) return 0;
    if(dp[i][lst]!=-1) return dp[i][lst];
    dp[i][lst]=1e18;
    for(auto u:adj[tab[i+1]]){
        dp[i][lst]=min(dp[i][lst],dfs(i+1,u.fi)+dst[to[lst][tab[i]]][to[u.fi][tab[i+1]]]);
    }
    //cout <<i<<" "<<lst<<" "<<dp[i][lst]<<endl; 
    return dp[i][lst];
}
int main(){
    /*#ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif*/
    cin>>n>>m>>t>>l;
    memset(dp,-1,sizeof dp);
    for (int i = 0; i < nax*2; ++i){
        for (int j = 0; j < nax*2; ++j)
        {   
            dst[i][j]=1e18;
        }
    }
    for (int i = 0; i < m; ++i)
    {
        int x,y,z;
        cin>>x>>y>>z;
        adj[x].pb({y,z});
        adj[y].pb({x,z});
    }
    for (int i = 0; i < l; ++i)
    {
        cin>>tab[i];
    }
    int x,y;
    cin>>x>>y;
    tab[x-1]=y;
    adj[tab[0]].pb({0,0});
    int cnt=0;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j < adj[i].size(); ++j)
        {
            to[adj[i][j].fi][i]=cnt;
            from[cnt]={adj[i][j].fi,i};
            cnt++;
        }
    }
    for (int i = 0; i < cnt; ++i)
    {
        djikastra(i);
    }
    /*for (int i = 0; i < cnt; ++i)
    {
        for (int j = 0; j < cnt; ++j)
        {
            cout << (dst[i][j]==1e18 ? -1 : dst[i][j]) <<" ";
        }cout <<endl;
    }*/
    long long ans=dfs(0,0);
    cout << (ans>=1e18 ? -1 :  ans)<<endl; 
}

• Subtask 1: 12 / 12
• Subtask 2: 35 / 35
• Subtask 3: 0 / 15
• Subtask 4: 0 / 38