結果
問題 | No.788 トラックの移動 |
ユーザー | nxteru |
提出日時 | 2020-04-13 17:30:24 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 432 ms / 2,000 ms |
コード長 | 4,277 bytes |
コンパイル時間 | 2,055 ms |
コンパイル使用メモリ | 181,492 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-05-08 23:03:30 |
合計ジャッジ時間 | 4,853 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 385 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 91 ms
5,376 KB |
testcase_05 | AC | 378 ms
5,376 KB |
testcase_06 | AC | 385 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 1 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 61 ms
5,376 KB |
testcase_16 | AC | 432 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; //#define LOCAL template<class T> struct Edge{ int s,t; T c; Edge(int x,T y):s(-1),t(x),c(y){} Edge(int x,int y,T z):s(x),t(y),c(z){} }; template<class T> using Edges=vector<Edge<T> >; template<class T> using Graph=vector<Edges<T> >; template<class T> vector<T>Dijkstra(int s,Graph<T>&g){ const T INF=numeric_limits<T>::max(); int n=g.size(); vector<T> d(n,INF); vector<int>pr(n,-1); priority_queue<pair<T,int>,vector<pair<T,int> >,greater<pair<T,int> > >pq; d[s]=0; pq.emplace(d[s],s); while(!pq.empty()){ T c=pq.top().first; int v=pq.top().second; pq.pop(); if(d[v]<c)continue; for(auto &e:g[v]){ int u=e.t; T l=e.c; if(d[u]>c+l){ d[u]=c+l; pr[u]=v; pq.emplace(d[u],u); } } } return d; } using ll=long long; #define rng(i,l,r) for(int i=int(l);i<int(r);i++) #define rep(i,r) rng(i,0,r) #define rrng(i,l,r) for(int i=int(r)-1;i>=int(l);i--) #define rrep(i,r) rrng(i,0,r) #define pb push_back #define eb emplace_back #define mp make_pair #define mt make_tuple #define one(x) memset(x,-1,sizeof(x)) #define zero(x) memset(x,0,sizeof(x)) #define F first #define S second #define bg begin() #define ed end() #define all(x) x.bg,x.ed #define si(x) int(x.size()) #define inf INT_MAX/2-100 #define infl LLONG_MAX/3 #ifdef LOCAL #define dmp(x) cerr<<__LINE__<<' '<<#x<<' '<<x<<endl #else #define dmp(x) void(0) #endif template<class t,class u>void chmax(t&a,u b){if(a<b)a=b;} template<class t,class u>void chmin(t&a,u b){if(b<a)a=b;} template<class t>using vc=vector<t>; template<class t>using vvc=vector<vector<t>>; using pi=pair<int,int>; using pl=pair<ll,ll>; using vi=vc<int>; using vl=vc<ll>; ll readl(void){ ll x; cin>>x; return x; } int readi(void){ int x; cin>>x; return x; } string readstr(){ string s; cin>>s; return s; } vi readvi(int n,int off=0){ vi v(n); rep(i,n)v[i]=readi(),v[i]+=off; return v; } vl readvl(int n,int off=0){ vl v(n); rep(i,n)v[i]=readl(),v[i]+=off; return v; } template<class t> void print(t x,int suc=1){ cout<<x; if(suc==1)cout<<"\n"; if(suc==2)cout<<" "; } template<class t> void print(const vc<t>&v,int suc=1){ rep(i,si(v))print(v[i],i==int(si(v))-1?1:suc); } template<class t> bool inc(t a,t b,t c){ return !(c<b||b<a); } template<class t> void compress(vc<t>&v){ sort(all(v)); v.erase(unique(all(v)),v.ed); } template<class t> int lwb(const vc<t>&v,const t&a){ return lower_bound(all(v),a)-v.bg; } template<class t> struct Compress{ vc<t>v; Compress()=default; Compress(const vc<t>&x){ add(x); } Compress(const initializer_list<vc<t> >&x){ for(auto &p:x)add(p); } void add(const t&x){ v.eb(x); } void add(const vc<t>&x){ copy(all(x),back_inserter(v)); } void build(){ compress(v); } int get(const t&x)const{ return lwb(v,x); } vc<t>get(const vc<t>&x)const{ vc<t>res(x); for(auto &p:res)p=get(p); return res; } const t &operator[](int x)const{ return v[x]; } }; void Yes(bool ex=true){ cout<<"Yes\n"; if(ex)exit(0); } void YES(bool ex=true){ cout<<"YES\n"; if(ex)exit(0); } void No(bool ex=true){ cout<<"No\n"; if(ex)exit(0); } void NO(bool ex=true){ cout<<"NO\n"; if(ex)exit(0); } void orYes(bool x,bool ex=true){ if(x)Yes(ex); else No(ex); } void orYES(bool x,bool ex=true){ if(x)YES(ex); else NO(ex); } void Possible(bool ex=true){ cout<<"Possible\n"; if(ex)exit(0); } void POSSIBLE(bool ex=true){ cout<<"POSSIBLE\n"; if(ex)exit(0); } void Impossible(bool ex=true){ cout<<"Impossible\n"; if(ex)exit(0); } void IMPOSSIBLE(bool ex=true){ cout<<"IMPOSSIBLE\n"; if(ex)exit(0); } void orPossible(bool x,bool ex=true){ if(x)Possible(ex); else Impossible(ex); } void orPOSSIBLE(bool x,bool ex=true){ if(x)POSSIBLE(ex); else IMPOSSIBLE(ex); } int main(void){ cin.tie(0); ios::sync_with_stdio(0); ll n=readl(),m=readl(),l=readl()-1; vl t=readvl(n); for(auto &i:t)dmp(i); Graph<ll> g(n); rep(i,m){ ll a=readl(),b=readl(),c=readl(); a--,b--; g[a].eb(b,c); g[b].eb(a,c); } vl dis=Dijkstra(l,g); ll ans=infl; rep(i,n){ dmp(i); ll r=infl,s=0; vl d=Dijkstra(i,g); rep(j,n){ if(i==j)continue; dmp(d[j]); s+=t[j]*d[j]*2LL; if(t[j])chmin(r,dis[j]-d[j]); } if(r==infl)r=0; chmin(ans,s+r); dmp(s+r); } print(ans); }