Submission #90121

#TimeUsernameProblemLanguageResultExecution timeMemory
90121Harvey_RollensEvacuation plan (IZhO18_plan)C++17
10 / 100
4091 ms56148 KiB
#include<bits/stdc++.h> #define ll long long #define ld long double #define st string #define fr first #define se second const ll mod=998244353; using namespace std; vector<pair<ll, ll> > v[100010]; priority_queue<pair<ll, ll> > q; ll a[100010], n, m, k, ans=0; map<ll, ll> dp[100200], us; void dej(ll xx) { for(ll i=1; i<=n; i++) dp[xx][i]=1e10; dp[xx][xx]=0; q.push({xx, dp[xx][xx]}); while(!q.empty()) { ll x=q.top().fr, s=q.top().se; q.pop(); if(s>dp[xx][x]) continue; for(ll i=0; i<v[x].size(); i++) { ll y=v[x][i].fr, p=v[x][i].se; if(dp[xx][x]+p<dp[xx][y]) { dp[xx][y]=dp[xx][x]+p; q.push({y, dp[xx][y]}); } } } } void dfs(ll x, ll y, ll mn) { us[x]=1; if(x==y) { ans=max(ans, mn); return; } for(ll i=0; i<v[x].size(); i++) { ll to=v[x][i].fr; if(!us[to]) { ll l=1e10; for(ll j=1; j<=k; j++) l=min(l, dp[a[j]][to]); dfs(to, y, min(mn, l)); } } } int main() { //freopen("1.txt", "r", stdin); //freopen("1.txt", "w", stdout); ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); cin>>n>>m; for(ll i=1; i<=m; i++) { ll x, y, z; cin>>x>>y>>z; v[x].push_back({y, z}); v[y].push_back({x, z}); } cin>>k; for(ll i=1; i<=k; i++) { cin>>a[i]; dej(a[i]); /*for(ll j=1; j<=n; j++) { cout<<dp[a[i]][j]<<" "; } cout<<endl;*/ } ll w; cin>>w; while(w--) { ll x, y; cin>>x>>y; //ans=0; //dfs(x, y, 1e10); //cout<<ans<<endl; //us.clear(); ll l=1e10; for(ll j=1; j<=k; j++) l=min(l, dp[a[j]][x]); for(ll j=1; j<=k; j++) l=min(l, dp[a[j]][y]); cout<<l<<endl; } return 0; } /* */

Compilation message (stderr)

plan.cpp: In function 'void dej(long long int)':
plan.cpp:32:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(ll i=0; i<v[x].size(); i++)
                     ~^~~~~~~~~~~~
plan.cpp: In function 'void dfs(long long int, long long int, long long int)':
plan.cpp:54:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ll i=0; i<v[x].size(); i++)
                 ~^~~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:116:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
         for(ll j=1; j<=k; j++)
         ^~~
plan.cpp:119:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
             cout<<l<<endl;
             ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...