Submission #76851999

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
typedef long long ll;
typedef pair<ll,int> pli;
const int N=2e5+5;
const ll INF=4e18;
int n,m;
ll Y;
vector<pli> g[N];
ll dist[N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>Y;
    rep(i,0,m){
        int u,v; ll t;
        cin>>u>>v>>t;
        g[u].push_back({t,v});
        g[v].push_back({t,u});
    }
    rep(i,1,n+1){
        ll x; cin>>x;
        g[i].push_back({x,0});
        g[0].push_back({x+Y,i});
    }
    rep(i,0,n+1) dist[i]=INF;
    priority_queue<pli,vector<pli>,greater<pli>> pq;
    dist[1]=0;
    pq.push({0,1});
    while(!pq.empty()){
        auto[d,u]=pq.top(); pq.pop();
        if(d>dist[u]) continue;
        for(auto[w,v]:g[u]){
            if(dist[u]+w<dist[v]){
                dist[v]=dist[u]+w;
                pq.push({dist[v],v});
            }
        }
    }
    rep(k,2,n+1){
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
typedef long long ll;
typedef pair<ll,int> pli;
const int N=2e5+5;
const ll INF=4e18;
int n,m;
ll Y;
vector<pli> g[N];
ll dist[N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>Y;
    rep(i,0,m){
        int u,v; ll t;
        cin>>u>>v>>t;
        g[u].push_back({t,v});
        g[v].push_back({t,u});
    }
    rep(i,1,n+1){
        ll x; cin>>x;
        g[i].push_back({x,0});
        g[0].push_back({x+Y,i});
    }
    rep(i,0,n+1) dist[i]=INF;
    priority_queue<pli,vector<pli>,greater<pli>> pq;
    dist[1]=0;
    pq.push({0,1});
    while(!pq.empty()){
        auto[d,u]=pq.top(); pq.pop();
        if(d>dist[u]) continue;
        for(auto[w,v]:g[u]){
            if(dist[u]+w<dist[v]){
                dist[v]=dist[u]+w;
                pq.push({dist[v],v});
            }
        }
    }
    rep(k,2,n+1){
        cout<<dist[k];
        if(k<n) cout<<' ';
    }
    cout<<"\n";
    return 0;
}

Submission Info

Judge Result