Submission #952336

#TimeUsernameProblemLanguageResultExecution timeMemory
952336vjudge306Relay Marathon (NOI20_relaymarathon)C++17
5 / 100
6097 ms235340 KiB
#include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> #define nn "\n" #define x_x ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define intt int _; cin >> _; while (_--) #define emp push_back #define mod 1000000007 #define all(v) v.begin(), v.end() #define ld long double #define A first #define B second //#define int long long typedef long long ll; const ld eps = 1e-27; // diff between decimals 0.000000001 mt19937 mt(time(nullptr)); struct ed { int f; int t; ll w; ed(int f, int t, ll w): f(f), t(t), w(w){} }; struct ss { bool operator()(ed a, ed b) { return a.w>b.w; } }; int main() { x_x int n,k,m; cin>>n>>m>>k; vector<ed>adj[n+2]; for (int i=0,a,b,c; i<m; i++) cin>>a>>b>>c, adj[a].emp({a,b,c}), adj[b].emp({b,a,c}); int sp[n+2]={}; ll dis[n+2]; for (int i=0,x;i<k; i++) cin>>x, sp[x]=1; vector<ed>v; for (int z=1; z<=n; z++) { if (!sp[z]) continue; for (auto&i:dis)i=1e15; dis[z]=0; priority_queue<ed, vector<ed>, ss>pq; pq.push({z,z,0}); while(!pq.empty()) { ed e=pq.top(); pq.pop(); if (dis[e.t]<(e.w)) continue; for(auto i:adj[e.t]) { ed nw={e.t, i.t, e.w+i.w}; if (dis[i.t]>nw.w) dis[i.t]=nw.w, pq.push(nw); } } for (int i=z+1; i<=n; i++) if (sp[i]&&dis[i]<1e15) v.emp({z,i,dis[i]}); } ll ans=LLONG_MAX; for (int i=0; i<v.size(); i++) { for (int j=i+1; j<v.size(); j++) if (v[i].f!=v[j].f&&v[i].t!=v[j].t&&v[i].f!=v[j].t&&v[i].t!=v[j].f) ans=min(ans, v[i].w+v[j].w); } cout<<ans; return 0; }

Compilation message (stderr)

RelayMarathon.cpp: In function 'int main()':
RelayMarathon.cpp:55:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ed>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for (int i=0; i<v.size(); i++) {
      |                   ~^~~~~~~~~
RelayMarathon.cpp:56:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ed>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int j=i+1; j<v.size(); j++)
      |                         ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...