제출 #1036187

#제출 시각아이디문제언어결과실행 시간메모리
1036187soncaoRobot (JOI21_ho_t4)C++17
24 / 100
235 ms69488 KiB
#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; }

컴파일 시 표준 에러 (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;
      |                 ~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...