이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
typedef long long ll;
vector <vector<pair <ll, pair<ll,ll> > > > adjl(1000000);
map <pair<ll,ll>, bool> probao;
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;
pair <ll,ll> drugi = make_pair(c,p);
u--, v--;
adjl[u].push_back(make_pair(v, drugi)), adjl[v].push_back(make_pair(u, drugi));
}
vector <ll> tmp(2,1000000000000000000);
vector <ll> cols(m + 1, 0);
vector <ll> mini(n, 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,-1))));
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;
dijk.pop();
if (col != 0 && pric > mini[u])
continue;
for (int i = 0; i < adjl[u].size(); i++){
ll v = adjl[u][i].first, c = adjl[u][i].second.first, p = adjl[u][i].second.second;
if (v != ori || col != 0)
cols[c] += p;
}
for (int i = 0; i < adjl[u].size(); i++){
ll v = adjl[u][i].first, c = adjl[u][i].second.first, p = adjl[u][i].second.second;
ll mu = u, mv = v;
if (cols[c] - p == 0 && mini[v] > pric)
mini[v] = pric, dijk.push(make_pair(-pric, make_pair(v, make_pair(u,c))));
if (cols[c] - p > 0){
ll most = cols[c] - p;
if (most + pric < mini[v])
mini[v] = pric + most, dijk.push(make_pair(-pric-most, make_pair(v, make_pair(u,c))));
if (p + pric < mini[v])
mini[v] = pric + p, probao[make_pair(mu,mv)] = true, dijk.push(make_pair(-pric-p, make_pair(v, make_pair(u,0))));
}
if (p + pric < mini[v]|| !probao[make_pair(mu,mv)])
mini[v] = min(mini[v], pric + p), probao[make_pair(mu,mv)] = true, dijk.push(make_pair(-pric-p, make_pair(v, make_pair(u,0))));
}
for (int i = 0; i < adjl[u].size(); i++){
ll v = adjl[u][i].first, c = adjl[u][i].second.first, p = adjl[u][i].second.second;
if (v != ori || col != 0)
cols[c] -= p;
}
}
if (mini[n-1] == 1000000000000000000)
cout << "-1";
else
cout << mini[n-1];
}
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp: In function 'int main()':
Main.cpp:49:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for (int i = 0; i < adjl[u].size(); i++){
| ~~^~~~~~~~~~~~~~~~
Main.cpp:57:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for (int i = 0; i < adjl[u].size(); i++){
| ~~^~~~~~~~~~~~~~~~
Main.cpp:82:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for (int i = 0; i < adjl[u].size(); i++){
| ~~^~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |