Submission #412995

#TimeUsernameProblemLanguageResultExecution timeMemory
412995ChaskaRobot (JOI21_ho_t4)C++11
0 / 100
1845 ms101140 KiB
#include <bits/stdc++.h> #define pb push_back #define sp " " #define sl "\n" #define fi first #define se second #define mp make_pair #define sz(a) ((int)a.size()) #define all(a) a.begin(),a.end() #define rev(a) reverse(a.begin(),a.end()) #define PI 3.141592 #define fo(i,n) for (int i=0;i<n;i++) #define fofo(i,n,j,m) for (int i=0;i<n;i++) for (int j=0;j<m;j++) using namespace std; typedef long long ll; typedef pair<ll,ll> ii; typedef pair<int,ii> iii; typedef vector<int> vi; typedef vector<ii> vii; const int N=1e5+5,M=2e5+5,mod=1e9+7; ll n,m; map<ll,ll> h[N]; map<ll,ll> hp[N]; vector<ll> g[N]; map<ii,ll> pr; map<ii,ll> co; bool vs[N]; ll res[N]; priority_queue<ii,vector<ii>,greater<ii>> pq; void dij(ll cost,ll node) { if (vs[node]) return; vs[node] = true; res[node] = cost; for (int u : g[node]) { if (!vs[u] && h[node][co[{node,u}]]==1) { pq.push({cost,u}); //dij(u,cost); } } for (int u : g[node]) { if (!vs[u]) if (h[node][co[{node,u}]]>1) { pq.push({cost+min(pr[{node,u}],hp[node][co[{node,u}]]-pr[{node,u}]),u}); //dij(u,cost); } } } int main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(); cin >> n >> m; for (int i=0;i<m;i++) { ll a,b,c,p; cin >> a >> b >> c >> p; co[{a,b}] = c; co[{b,a}] = c; pr[{a,b}] = p; pr[{b,a}] = p; g[a].push_back(b); g[b].push_back(a); h[a][c]++; hp[a][c] += p; h[b][c]++; hp[b][c] += p; } pq.push({0,1}); while (!pq.empty()) { auto x = pq.top(); pq.pop(); dij(x.fi,x.se); } if (!vs[n]) cout << -1; else cout << res[n]; return 0; } // Recuerda limites // Recuerda casos especiales
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...