이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <utility>
#include <map>
using namespace std;
typedef long long ll;
map<ll, vector <pair<ll, ll> > > adjl[100005];
map <ll, ll> boje[100005];
map <ll, ll> put[100005];
vector <vector <pair <ll, pair<ll, ll> > > > dadjl(100005);
int main()
{
ll n, m;
cin >> n >> m;
for (int i = 0; i < m; i++){
ll u, v, c, p;
cin >> u >> v >> c >> p;
u--, v--;
boje[u][c] += p;
boje[v][c] += p;
adjl[u][c].push_back(make_pair(v, p)), adjl[v][c].push_back(make_pair(u, p));
dadjl[u].push_back(make_pair(v, make_pair(c,p))), dadjl[v].push_back(make_pair(u, make_pair(c,p)));
}
vector <ll> mini(n + 1, 1000000000000000000);
mini[0] = 0;
priority_queue <pair <ll, pair<ll,pair<ll,ll> > > > dijk;
dijk.push(make_pair(0, make_pair(0, make_pair(-1,0))));
while (dijk.size()){
ll pric = -dijk.top().first, u = dijk.top().second.first, ori = dijk.top().second.second.first, col = dijk.top().second.second.first;
//if (pric == 0)
//cout << u << endl;
dijk.pop();
if (col > 0){
if (put[u][col] != pric)
continue;
for (pair <ll,ll> i : adjl[u][col]){
ll v = i.first, pri = i.second;
ll prelaz = boje[u][col] - pri + pric;
if (prelaz < mini[v])
mini[v] = prelaz, dijk.push(make_pair(-prelaz, make_pair(v, make_pair(u, 0))));
}
} else {
if (mini[u] != pric)
continue;
for (auto pp : dadjl[u]){
ll v = pp.first, c = pp.second.first, pri = pp.second.second;
ll prelaz = min(pric + boje[u][c] - pri, pric + pri);
// << prelaz << endl;
if (prelaz < mini[v])
mini[v] = prelaz, dijk.push(make_pair(-prelaz, make_pair(v, make_pair(u, 0))));
if (put[v].find(c) == put[v].end() || pric < put[v][c])
put[v][c] = pric, dijk.push(make_pair(-pric, make_pair(v, make_pair(u, c))));
}
}
}
if (mini[n-1] == 1000000000000000000)
cout << "-1";
else
cout << mini[n-1];
}
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp: In function 'int main()':
Main.cpp:47:67: warning: unused variable 'ori' [-Wunused-variable]
47 | ll pric = -dijk.top().first, u = dijk.top().second.first, ori = dijk.top().second.second.first, col = dijk.top().second.second.first;
| ^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |