이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
int aa , m , one , two , col;
long long p , ans[200001] , an[200001] , choto[200001] , chek[200001] , uttor;
vector<pair<pair<int , long long> , int>> arr[200001]; //first e col , then price , then node
priority_queue<pair<long long , int> , vector<pair<long long , int>> , greater<pair<long long , int>>> pq;
int main() {
cin >> aa >> m;
for( int z = 0; z < m; z++ ) {
cin >> one >> two >> col >> p;
arr[one].push_back({{col , p} , two});
arr[two].push_back({{col , p} , one});
}
for( int z = 1; z <= aa; z++ ) {
sort( arr[z].begin() , arr[z].end() );
}
ans[1] = 1;
pq.push({1 , 1});
while( !pq.empty() ) {
if( chek[pq.top().second] == 0 ) {
chek[pq.top().second] = 1;
one = pq.top().second;
ans[one] = pq.top().first;
two = arr[one].size();
for( int z = 0; z < two; z++ ) {
an[arr[one][z].first.first] += arr[one][z].first.second;
if(choto[arr[one][z].first.first] == 0 ) choto[arr[one][z].first.first] = ans[one];
if( ans[arr[one][z].second] != 0 ) {
choto[arr[one][z].first.first] = min( ans[arr[one][z].second] , choto[arr[one][z].first.first] );
}
}
for( int z = 0; z < two; z++ ) {
if( chek[arr[one][z].second] == 0 ) {
uttor = min( (min(arr[one][z].first.second , an[arr[one][z].first.first] - arr[one][z].first.second) + ans[one] ) , (an[arr[one][z].first.first] - arr[one][z].first.second) + choto[arr[one][z].first.first] );
pq.push({uttor , arr[one][z].second});
}
}
for( int z = 0; z < two; z++ ) {
an[arr[one][z].first.first] = 0;
choto[arr[one][z].first.first] = 0;
}
}
else pq.pop();
}
cout << ans[aa] - (long long)1;
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... |