이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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()
{
cin>>n>>m;
for(int i=1; i<=n; i++)
dp[i]=1e18;
for(int i=1; i<=m; i++)
{
int 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())
{
int cost=-pq.top().first;
int nod=pq.top().second;
if(nod==n)
{
cout<<cost<<'\n';
return 0;
}
pq.pop();
for(auto u:adj[nod])
{
int cost1=u.second.second;
int cost2=mp[nod][u.second.first]-cost1;
cost1=min(cost1,cost2);
if(dp[u.first]>cost1+dp[nod])
{
dp[u.first]=cost1+dp[nod];
pq.push({-dp[u.first],u.first});
}
}
}
if(dp[n]==1e18)
{
cout<<-1<<'\n';
return 0;
}
cout<<dp[n]<<'\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |