제출 #1176659

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1176659		AlgorithmWarrior	Robot (JOI21_ho_t4)	C++20	100 / 100	950 ms	92256 KiB

Main

#include <bits/stdc++.h>

using namespace std;

long long const INF=1e18;
int const MAX=1e5+5;

struct edge{
    int nod,col,pr;
};
vector<edge>G[MAX];
map<int,long long>dp[MAX];
map<int,vector<edge>>Gcol[MAX];
map<int,long long>sum[MAX];
int n,m;

void read(){
    cin>>n>>m;
    int i;
    for(i=1;i<=n;++i)
        dp[i][0]=INF;
    for(i=1;i<=m;++i){
        int u,v,col,pr;
        cin>>u>>v>>col>>pr;
        G[u].push_back({v,col,pr});
        G[v].push_back({u,col,pr});
        dp[u][col]=INF;
        dp[v][col]=INF;
        Gcol[u][col].push_back({v,col,pr});
        Gcol[v][col].push_back({u,col,pr});
        sum[u][col]+=pr;
        sum[v][col]+=pr;
    }
}

struct path{
    int nod,restr;
    long long dist;
};

class cmp{
public:
    bool operator()(path a,path b){
        return a.dist>b.dist;
    }
};

long long dijkstra(){
    priority_queue<path,vector<path>,cmp>pq;
    dp[1][0]=0;
    pq.push({1,0,0});
    while(!pq.empty()){
        auto [nod,restr,dist]=pq.top();
        pq.pop();
        if(dp[nod][restr]!=dist)
            continue;
        if(restr==0){
            for(auto [vec,col,pr] : G[nod]){
                if(dist+pr<dp[vec][0]){
                    dp[vec][0]=dist+pr;
                    pq.push({vec,0,dist+pr});
                }
                if(dist+sum[nod][col]-pr<dp[vec][0]){
                    dp[vec][0]=dist+sum[nod][col]-pr;
                    pq.push({vec,0,dist+sum[nod][col]-pr});
                }
                if(dist<dp[vec][col]){
                    dp[vec][col]=dist;
                    pq.push({vec,col,dist});
                }
            }
        }
        else{
            for(auto [vec,col,pr] : Gcol[nod][restr])
                if(dist+sum[nod][restr]-pr<dp[vec][0]){
                    dp[vec][0]=dist+sum[nod][restr]-pr;
                    pq.push({vec,0,dist+sum[nod][restr]-pr});
                }
        }
    }
    if(dp[n][0]==INF)
        dp[n][0]=-1;
    return dp[n][0];
}

int main()
{
    read();
    cout<<dijkstra();
    return 0;
}

• Subtask 1: 34 / 34
• Subtask 2: 24 / 24
• Subtask 3: 42 / 42