Submission #858526

#	Time	Username	Problem	Language	Result	Execution time	Memory
858526		damwuan	Robot (JOI21_ho_t4)	C++17	100 / 100	147 ms	30152 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=(j);i<=(k);i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
//#pragma GCC optimize("O2,unroll-loops")
//#pragma GCC target("avx,avx2,bmi,bmi2,sse,sse2,sse3,ssse3,sse4,popcnt")
#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
typedef vector<pii> vii;
typedef vector<int> vi;
const ll maxn=2e5+5;
const ll offset=1e18;
const ll block_sz=317;
const ll inf=1e18;
const ll mod=1e9+7;
int n,m;
struct Edge
{
    int v,c,p;
};
vector<Edge> adj[maxn];
priority_queue<pii,vii,greater<pii>> pq;
int sum[maxn],mn[maxn],dp[maxn];
void sol()
{
    cin >> n>>m;
    for1(i,1,m)
    {
        int u,v,c,p;cin >> u>> v>>c>>p;
        adj[u].pb({v,c,p});
        adj[v].pb({u,c,p});
    }
    for1(i,1,n) dp[i]=inf;
    pq.push({0,1});
    dp[1]=0;
    while (!pq.empty())
    {
        int x=pq.top().fi;
        int u=pq.top().se;
        pq.pop();
        if (dp[u]!=x) continue;
        for(Edge x:adj[u])
        {
            int v=x.v;
            int c=x.c;
            int p=x.p;
            sum[c]=0;
            mn[c]=inf;
        }

        for(Edge x:adj[u])
        {
            int v=x.v;
            int c=x.c;
            int p=x.p;
            sum[c]+=p;
            mn[c]=min(mn[c],dp[v]);//mn[c] la min dp[v1]
        }
        for(Edge x:adj[u])
        {
            int v=x.v;
            int c=x.c;
            int p=x.p;
            if (dp[v]>dp[u]+min(p,sum[c]-p))
            {
                dp[v]=dp[u]+min(p,sum[c]-p);
                pq.push({dp[v],v});
            }
            if (dp[v]>mn[c]+sum[c]-p)
            {
                dp[v]=mn[c]+sum[c]-p;
                pq.push({dp[v],v});
            }
        }
    }
    if (dp[n]>=inf) cout <<"-1";
    else cout << dp[n];
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t=1;//cin >> t;
    while (t--)
    {
        sol();
    }
}
/*

3 5 2 4 1
*/

Compilation message (stderr)

Main.cpp: In function 'void sol()':
Main.cpp:55:17: warning: unused variable 'v' [-Wunused-variable]
   55 |             int v=x.v;
      |                 ^
Main.cpp:57:17: warning: unused variable 'p' [-Wunused-variable]
   57 |             int p=x.p;
      |                 ^

• Subtask 1: 34 / 34
• Subtask 2: 24 / 24
• Subtask 3: 42 / 42