이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=5005, INF=1e18;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m; cin >> n >> m;
vector<vector<array<int, 2>>> g(n);
vector<int> c(m), p(m), u(m), v(m);
map<int, int> s[n], dpp[n], pos[n];
vector<int> dp(n, INF);
for(int i=0; i<m; i++){
cin >> u[i] >> v[i] >> c[i] >> p[i];
u[i]--; v[i]--;
if(u[i] > v[i]) swap(u[i], v[i]);
g[u[i]].push_back({v[i], i});
g[v[i]].push_back({u[i], i});
s[u[i]][c[i]]+=p[i];
s[v[i]][c[i]]+=p[i];
}
for(int i=0; i<n; i++){
if(!g[i].size()) continue;
sort(g[i].begin(), g[i].end(), [&](auto x, auto y){
return c[x[1]] < c[y[1]];
});
for(int l=0; l<g[i].size(); l++){
int col=c[g[i][l][1]];
if(pos[i].count(col)) continue;
pos[i][col] = l;
}
}
priority_queue<array<int, 3>> pq;
dp[0]=0;
pq.push({0, 0, -1});
int ans = INF;
while(pq.size()){
auto [cost, v, color] = pq.top();
pq.pop(); cost*=-1;
if(v==n-1){
ans=min(ans, cost);
}
if(color == -1){
if(dp[v] != cost) continue;
for(auto [i, j]: g[v]){
if(dp[i] > cost+p[i]){
dp[i] = cost+p[i];
pq.push({-dp[i], i, -1});
}
if(dp[i] > cost+s[i][c[j]]-p[j]){
dp[i] = cost+s[i][c[j]]-p[j];
pq.push({-dp[i], i, -1});
}
if(!dpp[i].count(c[j]) || dpp[i][c[j]] > cost){
dpp[i][c[j]] = cost;
pq.push({-cost, i, c[j]});
}
}
}
else{
if(cost != dpp[v][color]) continue;
for(int l=pos[v][color]; l<g[v].size(); l++){
auto [i, j]=g[v][l];
if(c[j] != color) break;
else{
int val = cost+s[i][c[j]]-p[j];
if(dp[i] > val){
dp[i] = val;
pq.push({-val, i, -1});
}
}
}
}
}
if(ans == INF) cout<<-1;
else cout<<ans;
}
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp: In function 'int main()':
Main.cpp:34:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for(int l=0; l<g[i].size(); l++){
| ~^~~~~~~~~~~~
Main.cpp:76:39: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for(int l=pos[v][color]; l<g[v].size(); l++){
| ~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |