Source Code
#include<bits/stdc++.h>
using namespace std;
#define double long double
#define ll long long
#define Test int T;cin>>T;while(T--)
#define pi acos(-1)
#define endl "\n"
#define fx(x) fixed<<setprecision(x)
#define sz(s) (int)s.size()
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define mem(a,n) memset((a),n,sizeof (a))
#define INF 1e9
#define ii pair<ll,ll>
ll gcd(ll x,ll y){return(!y?x:gcd(y,x%y));}
ll lcm(ll x,ll y){return x/gcd(x,y)*y;}
void file(){
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#else
    //freopen("journey.in", "r", stdin);
    //freopen("journey.out", "w", stdout);
#endif
}
void fast(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    file();
}
int dx[]= {0,0,1,-1};
int dy[]= {-1,1,0,0};
const double eps=1e-9;
const int mod=1e9+7;
const int N=3e5+5;
int main(){
    fast();
    int n,q;
    cin>>n>>q;
    set<int>st;
    vector<ll>v(n+1);
    vector<pair<int,int> >adj(n+1);
    for(int i=1;i<=n;i++){
        cin>>v[i];
        st.insert(i);
        adj[i]={10000000,0};
    }
    while(q--){
        int a,b,c;
        cin>>a>>b>>c;
        if(b>c)swap(b,c);
        adj[a].first=min(adj[a].first,b);
        adj[a].second=max(adj[a].second,c);
    }
    priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > >qe;
    vector<ll>dis(n+1,-1);
    dis[1]=0;
    st.erase(1);
    qe.push({0,1});
    while(!qe.empty()){
        auto cur=qe.top();
        qe.pop();
        for(auto it=st.lower_bound(adj[cur.second].first);it!=st.end();){
            int x=*it;
            if(x>adj[cur.second].second)break;
            assert(dis[x]==-1);
            if(dis[x]!=-1)continue;
            dis[x]=dis[cur.second]+abs(v[x]-v[cur.second]);
            qe.push({dis[x],x});
            st.erase(x);
            it=st.lower_bound(adj[cur.second].first);
        }
    }
    for(int i=1;i<=n;i++)
        cout<<dis[i]<<" ";
    cout<<endl;
    return 0;
}
Copy
Fallout: New Vegas mahmoud_ashour
GNU G++17
0 ms
824 KB
Wrong Answer