제출 #1221309

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1221309		amine_aroua	Wild Boar (JOI18_wild_boar)	C++20	62 / 100	10473 ms	798492 KiB

wild_boar

#include<bits/stdc++.h>
// #pragma GCC optimize("O3" , "unroll-loops")
// #include <ext/pb_ds/assoc_container.hpp>
using namespace std;
// using namespace __gnu_pbds;
// template <class T>
// using Tree = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
using ll = long long;
int floor_div(int x, int y) {
	assert(y != 0);
	if (y < 0) {
		y = -y;
		x = -x;
	}
	if (x >= 0) return x / y;
	return (x + 1) / y - 1;
}
int ceil_div(int x, int y) {
	assert(y != 0);
	if (y < 0) {
		y = -y;
		x = -x;
	}
	if (x <= 0) return x / y;
	return (x - 1) / y + 1;
}

const int N = 2000;
const int C = 3;
const int L = (1<<17);
const ll INF = 1e18;


int n , m , t , l;

vector<pair<int ,ll>> adj[N + 1];
int invadj[N + 1][N + 1];
vector<vector<vector<vector<ll>>>> dist(N+1 , vector<vector<vector<ll>>>(N+1 , vector<vector<ll>>()));

void run_case()
{
    cin>>n>>m>>t>>l;
    for(int i = 1 ; i <= n ;i++)
    {
        invadj[i][0] = 0;
        adj[i].push_back({0 , 0});
    }
    for(int i = 0 ; i < m ;i++)
    {
        int u , v , c;
        cin>>u>>v>>c;
        invadj[u][v] = (int)adj[u].size();
        adj[u].push_back({v , c});
        invadj[v][u] = (int)adj[v].size();
        adj[v].push_back({u , c});
    }
    for(int i = 1 ;i <= n ; i++)
    {
        for(int j = 1 ; j <= n ; j++)
        {
            dist[i][j].assign((int)adj[i].size() , vector<ll>((int)adj[j].size() , INF));   
        }
    }
    vector<vector<bool>> vis(m + 1 , vector<bool>(n + 1));
    for(int i = 1 ; i <= n ; i++)
    {
        for(int j = 0 ; j < (int)adj[i].size() ; j++)
        {
            priority_queue<pair<ll , pair<int ,int>>> pq;
            dist[i][i][j][j] = 0;
            pq.push({0 , {j , i}});
            vis.assign(m + 1 , vector<bool>(n + 1 , 0));
            while(!pq.empty())
            {
                auto tp = pq.top();
                pq.pop();
                ll d = -tp.first;
                auto [edgprv , cur] = tp.second;
                if(vis[edgprv][cur])
                    continue;
                vis[edgprv][cur] = 1;
                int prv = adj[cur][edgprv].first;
                for(auto [u , c] : adj[cur])
                {
                    if(u != prv && u)
                    {
                        int edgu = invadj[u][cur];
                        if(dist[i][u][j][edgu] > d + c)
                        {
                            dist[i][u][j][edgu] = d + c;
                            pq.push({-(d + c) , {edgu , u}});
                        }   
                    }
                }
            }
        }
    }
    vector<ll> dp(m + 1 , INF);
    vector<int> x(l);
    for(auto &u : x)
        cin>>u;
    int p , q;
    cin>>p>>q;
    p--;
    x[p] = q;
    dp[0] = 0;
    vector<ll> ndp(m + 1 ,INF);
    ll ans = INF;
    for(int i = 1 ; i < l ; i++)
    {
        ndp.assign(m + 1 , INF);
        int u = x[i] , v = x[i - 1];
        int mnpos = 0;
        for(int j = 0 ; j < (int)adj[v].size() ; j++)
        {
            if(dp[mnpos] > dp[j])
            {
                mnpos = j;
            }
        }
        int semnpos = (mnpos + 1);
        if(semnpos == (int)adj[v].size())
            semnpos = 0;
        for(int j = 0 ; j < (int)adj[v].size() ; j++)
        {
            if(j == mnpos)
                continue;
            if(dp[semnpos] > dp[j])
            {
                semnpos = j;
            }
        }
        vector<int> curv = {mnpos , semnpos};
        for(int prvu = 1 ; prvu < (int) adj[u].size() ; prvu++)
        {
            for(int prvv : curv)
            {
                ndp[prvu] = min(ndp[prvu] , dp[prvv]+ dist[v][u][prvv][prvu]);
            }
            if(i == l - 1)
                ans = min(ans , ndp[prvu]);
        }
        dp = ndp;
    }
    cout<<(ans >= INF ? -1 : ans)<<'\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin>>t;
    while(t--)
    {
        run_case();
    }
}
// THINK OF DP !
// KEEP TRACK OF TIME !

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