| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1161371 | brinton | Robot (JOI21_ho_t4) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf (long long)(1e15)
signed main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
//start here
int N,M;
cin >> N >> M;
vector<vector<array<int,3>>> edges(N+1);
vector<map<int,int>> total(N+1);
for(int i = 0;i < M;i++){
int a,b,color,cost;
cin >> a >> b >> color >> cost;
edges[a].push_back({b,color,cost});
edges[b].push_back({a,color,cost});
total[a][color] += cost;
total[b][color] += cost;
}
// vector<vector<int>> dist(N+1,vector<int>(M+2,inf));
map<pair<int,int>,int> dist;
priority_queue<array<int,3>,vector<array<int,3>>,greater<array<int,3>>> pq;
// M+1 is king
dist[{1,M+1}] = 0;
dist[{1,M+1}] = 0;
pq.push({0,1,M+1});// dist,idx,in_color
while(!pq.empty()){
auto [cdist,cur,ccolor] = pq.top();
// cout << cur << " " << ccolor << " : " << cdist << " " << dist[cur][ccolor] << endl;
pq.pop();
if(dist[{cur,ccolor}] != cdist)continue;
// cout << cur << " " << ccolor << " : " << cdist << endl;
if(ccolor == M+1){
// this is a king node
// cout << "A" << endl;
for(auto [nxt,color,w]:edges[cur]){
// cout << nxt << " " << endl;
// to color node, chose direct
if(!dist.count({nxt,color}) || cdist+w-w < dist[{nxt,color}]){
dist[{nxt,color}] = cdist+w-w;
pq.push({dist[{nxt,color}],nxt,color});
}
// to king node, chose direct or indirect
int ndist = cdist+min(w,total[cur][color]-w);
if(!dist.count({nxt,M+1}) || ndist < dist[{nxt,M+1}]){
dist[{nxt,M+1}] = ndist;
pq.push({ndist,nxt,M+1});
}
}
}else{
// cout << "A" << endl;
for(auto [nxt,color,w]:edges[cur]){
// choose other, so become king node
if(color == ccolor && total[cur][color]-w+cdist < dist[{nxt,M+1}]){
dist[{nxt,M+1}] = total[cur][color]-w+cdist;
pq.push({dist[{nxt,M+1}],nxt,M+1});
}
}
}
}
if(!dist.count({N,M+1}) == inf){
cout << "-1";
}else{
cout << dist[N][M+1];
}
}