結果
問題 | No.2712 Play more! |
ユーザー |
|
提出日時 | 2024-03-31 14:48:56 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,760 bytes |
コンパイル時間 | 1,442 ms |
コンパイル使用メモリ | 172,620 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-09-30 19:59:34 |
合計ジャッジ時間 | 2,952 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 WA * 2 |
ソースコード
#include "bits/stdc++.h"/*#include "boost/multiprecision/cpp_int.hpp"namespace mp = boost::multiprecision;using i128=mp::cpp_int;*/using namespace std;typedef long long ll;typedef int64_t i64;typedef vector<int> vi;typedef vector<vi> vvi;typedef vector<vvi> vvvi;typedef vector<ll> vll;typedef vector<vll> vvll;typedef vector<vvll> vvvll;typedef vector<string> vs;typedef vector<char> vc;typedef vector<vc> vvc;typedef vector<double> vd;typedef vector<vd> vvd;#define rep(i,a,n) for(int i=a;i<n;i++)#define drep(i,a,n) for(int i=a;i>n;i--)#define yes(ans) if(ans)cout<<"yes"<<endl;else cout<<"no"<<endl;#define Yes(ans) if(ans)cout<<"Yes"<<endl;else cout<<"No"<<endl;#define YES(ans) if(ans)cout<<"YES"<<endl;else cout<<"NO"<<endl;#define iINF 1000000007#define lINF 10000000000007#define llINF 4000000000000000007#define all(x) x.begin(),x.end()#define so(x) sort(all(x))#define re(x) reverse(all(x))const double PI = acos(-1);//ベルマンフォードstruct edges{ll from;ll to;ll cost;};using ve=vector<edges>;bool bellman(ve &miti,ll s,vll &dist,ll m){ //返り値 なし(副作用 distが変わる)dist[s]=0;ll y=1;ll cnt=0;while(y){if(cnt>m){return 1;}y=0;for(auto i:miti){if(dist[i.from]+i.cost<dist[i.to]){dist[i.to]=dist[i.from]+i.cost;y=1;}}cnt++;}return 0;}int main(){ll n,m; cin>>n>>m;vll d(n); rep(i,0,n) cin>>d[i];ve miti(m);ll a,b,c;rep(i,0,m){cin>>a>>b>>c; a--; b--;miti[i]={a,b,c-d[a]};}vll dist(n,llINF);bool y=bellman(miti,0,dist,m);//cout<<dist[n-1]<<endl;if(y) cout<<"inf"<<endl;else cout<<d[n-1]-dist[n-1]<<endl;}