結果

問題 No.3653 Space-Time Courier
コンテスト
ユーザー askr58
提出日時 2026-08-28 22:25:54
言語 C++23
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 43 ms / 4,000 ms
+ 396µs
コード長 4,623 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,051 ms
コンパイル使用メモリ 343,388 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2026-08-28 22:26:31
合計ジャッジ時間 5,946 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <random>
#include <chrono>
#include <iomanip>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <string>
#include <stack>
#include <ranges>
#include <algorithm>
#include <vector>
using namespace std;
using ll=long long;

#include <atcoder/all>
using mint=atcoder::modint998244353;

ostream& operator<<(ostream& os,const mint& x){
	os<<x.val();
	return os;
}
istream& operator>>(istream& is,mint& x){
	int t;
	is>>t;
	x=t;
	return is;
}

template <typename S,typename T>
ostream& operator<<(ostream& os,const pair<S,T>& p);
template <typename S,typename T>
istream& operator>>(istream& is,pair<S,T>& p);
template <typename T,size_t n>
ostream& operator<<(ostream& os,const array<T,n>& arr);
template <typename T,size_t n>
istream& operator>>(istream& is,array<T,n>& arr);
template <typename T>
ostream& operator<<(ostream& os,const vector<T>& vec);
template <typename T>
istream& operator>>(istream& is,vector<T>& vec);

template <typename S,typename T>
ostream& operator<<(ostream& os,const pair<S,T>& p){
	os<<p.first<<" "<<p.second;
	return os;
}
template <typename S,typename T>
istream& operator>>(istream& is,pair<S,T>& p){
	is>>p.first>>p.second;
	return is;
}

template <typename T,size_t n>
ostream& operator<<(ostream& os,const array<T,n>& arr){
	for(int i=0;i<n;i++)os<<arr[i]<<(i+1==n?"":" ");
	return os;
}
template <typename T,size_t n>
istream& operator>>(istream& is,array<T,n>& arr){
	for(int i=0;i<n;i++)is>>arr[i];
	return is;
}
template <typename T>
ostream& operator<<(ostream& os,const vector<T>& vec){
	for(int i=0;i<vec.size();i++)os<<vec[i]<<(i+1==vec.size()?"":" ");
	return os;
}
template <typename T>
istream& operator>>(istream& is,vector<T>& vec){
	for(int i=0;i<vec.size();i++)is>>vec[i];
	return is;
}

template<class... Vecs>
void input_vec(Vecs&... vs) {
    const auto n = get<0>(tie(vs...)).size();

    for (size_t i = 0; i < n; ++i)
        ((cin >> vs[i]), ...);
}

template <typename T>
vector<T> make_unique(vector<T> vec){
	ranges::sort(vec);
	vec.erase(unique(vec.begin(),vec.end()),vec.end());
	return vec;
}

template <typename T, typename Comp = ranges::less, typename Proj = identity>
pair<vector<int>,vector<int>> make_rank(const vector<T>& vec, Comp comp = {}, Proj proj = {}) {
    int n = vec.size();
    vector<int> argsort(n);
    iota(argsort.begin(), argsort.end(), 0);

    ranges::stable_sort(argsort, comp, [&](int i) -> decltype(auto) {
        return invoke(proj, vec[i]);
    });

	vector<int> rank(n);
	for(int i=0;i<n;i++)rank[argsort[i]]=i;
    return make_pair(rank,argsort);
}

using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using vvvl=vector<vector<vector<ll>>>; 
using vi=vector<int>;
using vvi=vector<vector<int>>;
using vvvi=vector<vector<vector<int>>>;
int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	int n,m;
	cin>>n>>m;
	vl p(n);
	cin>>p;
	vi u(m),v(m);
	vl t(m);
	input_vec(u,v,t);
	for(int i=0;i<m;i++)u[i]--,v[i]--;
	using P=pair<ll,int>;
	ll inf=1e18;
	vector<P> dp(n,P{inf,-1}),ep(n,P{inf,-1});
	for(int i=0;i<n;i++)dp[i]=P{p[i],i};
	auto update=[&](int i,int j,ll w)->void{
		if(dp[i].second!=-1){
			if(dp[j].first>dp[i].first+w){
				if(dp[j].second!=dp[i].second&&dp[j].second!=-1){
					ep[j]=dp[j];
				}
				dp[j]=P{dp[i].first+w,dp[i].second};
			}else if(ep[j].first>dp[i].first+w&&dp[j].second!=dp[i].second){
				ep[j]=P{dp[i].first+w,dp[i].second};
			}
		}
		if(ep[i].second!=-1){
			 if(ep[j].first>ep[i].first+w&&dp[j].second!=ep[i].second){
				ep[j]=P{ep[i].first+w,ep[i].second};
			}
		}
	};


	for(int tt=0;tt<n+1;tt++){
	/*
		cout<<tt<<endl;
		for(int i=0;i<n;i++){
			cout<<dp[i]<<","<<ep[i]<<endl;
		}
		*/
		for(int i=0;i<m;i++){
			update(u[i],v[i],t[i]);
		}
	}
	vl a(n);
	ll ans=inf;
	for(int i=0;i<n;i++){
		if(dp[i].second!=i){
			a[i]=dp[i].first+p[i];
			ans=min(ans,a[i]);
		}else{
			a[i]=ep[i].first+p[i];
			ans=min(ans,a[i]);
		}
	}
	ll cnt=0;
	vector<vector<pair<ll,int>>> revgraph(n);
	for(int i=0;i<m;i++)revgraph[v[i]].push_back(P{t[i],u[i]});
	for(int i=0;i<n;i++){
		if(a[i]!=ans)continue;
		queue<int> bfs;
		bfs.push(i);
		vl seen(n,inf);
		seen[i]=a[i]-p[i];
		while(!bfs.empty()){
			int x=bfs.front();
			bfs.pop();
			for(auto[w,y]:revgraph[x]){
				if(seen[y]!=inf)continue;
				if(dp[y].second!=i){
					if(dp[y].first+w==seen[x]){
						seen[y]=dp[y].first;
						bfs.push(y);
					}
				}else{
					if(ep[y].first+w==seen[x]){
						seen[y]=ep[y].first;
						bfs.push(y);
					}
				}
			}
		}
		for(int j=0;j<n;j++)if(i!=j&&seen[j]==p[j])cnt++;
	}
	cout<<ans<<" "<<cnt<<endl;
}
0