제출 #1084002

#제출 시각아이디문제언어결과실행 시간메모리
1084002I_FloPPed21Robot (JOI21_ho_t4)C++14
0 / 100
171 ms42812 KiB
#include <bits/stdc++.h> using namespace std; const int N=1e5+1; const int M=2e5+1; int n,m; unordered_map<int,long long>mp[N]; vector<pair<int,pair<int,long long>>>adj[N]; long long dp[N]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m; for(int i=1; i<=n; i++) dp[i]=1e18; for(int i=1; i<=m; i++) { long long a,b,color,c; cin>>a>>b>>color>>c; adj[a].push_back({b,{color,c}}); adj[b].push_back({a,{color,c}}); mp[a][color]+=c; mp[b][color]+=c; } dp[1]=0; priority_queue<pair<long long,int>> pq={}; pq.push({0,1}); while(!pq.empty()) { long long cost=-pq.top().first; int nod=pq.top().second; pq.pop(); for(auto u:adj[nod]) { long long cost1=u.second.second; long long cost2=mp[nod][u.second.first]-cost1; cost1=min(cost1,cost2); if(dp[u.first]>cost1+cost) { dp[u.first]=cost1+cost; pq.push({-dp[u.first],u.first}); } } } if(dp[n]==1e18) { cout<<-1<<'\n'; return 0; } cout<<dp[n]<<'\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...