Submission #1067565

#TimeUsernameProblemLanguageResultExecution timeMemory
1067565Dennis_JasonConstruction Project 2 (JOI24_ho_t2)C++14
0 / 100
2099 ms14332 KiB
#include <bitset> #include <cmath> #include <functional> #include <algorithm> #include <numeric> #include <deque> #include <fstream> #include <iomanip> #include <iostream> #include <iterator> #include <limits> #include <list> #include <map> #include <unordered_map> #include <queue> #include <set> #include <stack> #include <string> #include <vector> #include <cstring> #include <climits> #define pb push_back #define MOD 1000000007 #define NMAX 200001 #define nl '\n' #define INF 1000000007 #define pii1 pair<int, pair<int,int>> (1,(1,2)); #define pii pair<int,int> #define tpl tuple<int,int,int,int,int> using namespace std; ifstream fin("data.in"); ofstream fout("data.out"); /* ====================DEMONSTRATION====================== =========================END=========================== */ int n,m,s,t,l,k; vector<int>v; vector<vector<pii>>G(NMAX); vector<int>dist_s,dist_t; priority_queue<pii,vector<pii>,greater<pii>>pq; void dijkstra(int node,vector<int>&dist) { for(int i=0;i<n;++i) dist[i]=INF; dist[node]=0; pq.push({0,node}); while(!pq.empty()) { auto [dis,first]=pq.top(); pq.pop(); if(dist[first]<dis) continue; for(auto [u,w]:G[node]) { if(dist[u]>dist[first]+w) { dist[u]=dist[first]+w; pq.push({dist[u],u}); } } } } signed main() { cin>>n>>m; cin>>s>>t>>l>>k; s--; t--; dist_s.resize(n); dist_t.resize(n); for(int i=1;i<=m;++i) { int x,y,c; cin>>x>>y>>c; x--; y--; G[x].pb({y,c}); G[y].pb({x,c}); } dijkstra(s,dist_s); dijkstra(t,dist_t); if(dist_s[t]<=k) { cout<<(n*(n-1)/2); return 0; } sort(dist_t.begin(),dist_t.end()); int ans=0; for(int i=0;i<n;++i) { int dis=k-l-dist_s[i]; int pos= lower_bound(dist_t.begin(),dist_t.end(),dis+1)-dist_t.begin(); ans+=pos; } cout<<ans; return 0; }

Compilation message (stderr)

Main.cpp: In function 'void dijkstra(int, std::vector<int>&)':
Main.cpp:56:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |         auto [dis,first]=pq.top();
      |              ^
Main.cpp:60:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |         for(auto [u,w]:G[node])
      |                  ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...