Submission #1036187

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036187		soncao	Robot (JOI21_ho_t4)	C++17	24 / 100	235 ms	69488 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<int,int>
#define lll pair<ll,ll>
#define vi vector<int>
#define vvi vector<vector<int>>

const ll oo=1e18;
const int N=6e5+5;

vector<ii> a[N];
vector<pair<int,ii>> g[N];
ll dist[N],sum[N];
bool vis[N];

void dij(int x){
    for(int i=1;i<=N;i++)dist[i]=1e18;
    priority_queue<ii,vector<ii>,greater<ii>> q;
    dist[x]=0;
    q.push({0,x});
    while(!q.empty()){
        auto p1=q.top();q.pop();
        int W=p1.first,x=p1.second;
        if(vis[x])continue;
        vis[x]=1;
        for(auto p2:a[x]){
            int y=p2.first,w=p2.second;
            if(vis[y]||dist[y]<W+w)continue;
            dist[y]=W+w;
            q.push({W+w,y});
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
   // freopen("permute.inp","r",stdin);
   // freopen("permute.out","w",stdout);

    int n,m,x,y,c,p;
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        cin>>x>>y>>c>>p;
        g[x].push_back({c,{y,p}});
        g[y].push_back({c,{x,p}});
        a[x].push_back({y,p});
        a[y].push_back({x,p});
    }
    int cur=n;
    for(int i=1;i<=n;++i){
        sort(g[i].begin(),g[i].end());
        for(auto x:g[i])
            sum[x.first]+=x.second.second;
        for(auto x:g[i]){
            if(!vis[x.first]){
                ++cur;
                a[i].push_back({cur,0});
            }
            vis[x.first]=1;
            a[cur].push_back({x.second.first,sum[x.first]-x.second.second});
            a[x.second.first].push_back({cur,0});
        }
        for(auto x:g[i]){
            sum[x.first]=0;
            vis[x.first]=0;
        }
    }

    dij(1);
    if(dist[n]==oo)
        cout<<"-1";
    else
        cout<<dist[n];

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void dij(int)':
Main.cpp:18:33: warning: iteration 600004 invokes undefined behavior [-Waggressive-loop-optimizations]
   18 |     for(int i=1;i<=N;i++)dist[i]=1e18;
      |                          ~~~~~~~^~~~~
Main.cpp:18:18: note: within this loop
   18 |     for(int i=1;i<=N;i++)dist[i]=1e18;
      |                 ~^~~

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