Submission #1102710

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102710		ttamx	Robot (JOI21_ho_t4)	C++17	34 / 100	3060 ms	58352 KiB

Main

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

const int N=100'005;
const int M=200'005;
const ll INF=LLONG_MAX/2;

int n,m;
int eu[M],ev[M],ec[M],ew[M];
vector<tuple<int,int,int>> adj[N];
vector<int> id[N];
vector<ll> sum[N];
vector<array<ll,2>> dp[N];
vector<array<bool,2>> vis[N];
priority_queue<tuple<ll,int,int,int>,vector<tuple<ll,int,int,int>>,greater<tuple<ll,int,int,int>>> pq;

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m;
    for(int i=0;i<m;i++){
        cin >> eu[i] >> ev[i] >> ec[i] >> ew[i];
        adj[eu[i]].emplace_back(ev[i],id[eu[i]].size(),id[ev[i]].size());
        adj[ev[i]].emplace_back(eu[i],id[ev[i]].size(),id[eu[i]].size());
        id[eu[i]].emplace_back(i);
        id[ev[i]].emplace_back(i);
    }
    for(int i=1;i<=n;i++){
        int k=id[i].size();
        dp[i].assign(k,{INF,INF});
        vis[i].assign(k,{false,false});
        sum[i].assign(k,0);
    }
    for(int u=1;u<=n;u++){
        map<int,ll> mp;
        for(auto [v,ui,vi]:adj[u]){
            int cc=ec[id[u][ui]];
            int ww=ew[id[u][ui]];
            mp[cc]+=ww;
        }
        for(int i=0;i<id[u].size();i++){
            sum[u][i]=mp[ec[id[u][i]]];
        }
    }
    for(auto [v,ui,vi]:adj[1]){
        int cc=ec[id[1][ui]];
        int ww=ew[id[1][ui]];
        dp[v][vi][0]=sum[1][ui]-ww;
        dp[v][vi][1]=ww;
        pq.emplace(dp[v][vi][0],v,vi,0);
        pq.emplace(dp[v][vi][1],v,vi,1);
    }
    while(!pq.empty()){
        auto [d,u,i,t]=pq.top();
        pq.pop();
        if(vis[u][i][t])continue;
        vis[u][i][t]=true;
        if(u==n){
            cout << d;
            exit(0);
        }
        int c=ec[id[u][i]];
        int w=ew[id[u][i]];
        for(auto [v,ui,vi]:adj[u]){
            if(ui==i)continue;
            int cc=ec[id[u][ui]];
            int ww=ew[id[u][ui]];
            ll d0=d+sum[u][ui]-ww-(t&&c==cc?w:0);
            ll d1=d+ww;
            if(d0<dp[v][vi][0]){
                dp[v][vi][0]=d0;
                pq.emplace(d0,v,vi,0);
            }
            if(d1<dp[v][vi][1]){
                dp[v][vi][1]=d1;
                pq.emplace(d1,v,vi,1);
            }
        }
    }
    cout << -1;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:43:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         for(int i=0;i<id[u].size();i++){
      |                     ~^~~~~~~~~~~~~
Main.cpp:48:13: warning: unused variable 'cc' [-Wunused-variable]
   48 |         int cc=ec[id[1][ui]];
      |             ^~

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