結果
問題 | No.1344 Typical Shortest Path Sum |
ユーザー | soraie_ |
提出日時 | 2021-02-11 16:05:54 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 5,448 bytes |
コンパイル時間 | 2,233 ms |
コンパイル使用メモリ | 220,068 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-18 04:53:30 |
合計ジャッジ時間 | 4,316 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 1 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | AC | 1 ms
6,944 KB |
testcase_06 | AC | 2 ms
6,944 KB |
testcase_07 | AC | 1 ms
6,940 KB |
testcase_08 | AC | 1 ms
6,940 KB |
testcase_09 | AC | 1 ms
6,944 KB |
testcase_10 | AC | 2 ms
6,944 KB |
testcase_11 | AC | 1 ms
6,940 KB |
testcase_12 | AC | 2 ms
6,944 KB |
testcase_13 | AC | 2 ms
6,940 KB |
testcase_14 | AC | 2 ms
6,940 KB |
testcase_15 | AC | 2 ms
6,944 KB |
testcase_16 | AC | 2 ms
6,940 KB |
testcase_17 | AC | 2 ms
6,940 KB |
testcase_18 | AC | 2 ms
6,944 KB |
testcase_19 | AC | 2 ms
6,944 KB |
testcase_20 | AC | 2 ms
6,944 KB |
testcase_21 | AC | 2 ms
6,944 KB |
testcase_22 | AC | 2 ms
6,940 KB |
testcase_23 | AC | 2 ms
6,944 KB |
testcase_24 | AC | 1 ms
6,940 KB |
testcase_25 | AC | 2 ms
6,940 KB |
testcase_26 | AC | 1 ms
6,940 KB |
testcase_27 | AC | 2 ms
6,944 KB |
testcase_28 | AC | 2 ms
6,944 KB |
testcase_29 | AC | 2 ms
6,940 KB |
testcase_30 | AC | 1 ms
6,944 KB |
testcase_31 | AC | 2 ms
6,940 KB |
testcase_32 | AC | 1 ms
6,940 KB |
testcase_33 | AC | 1 ms
6,944 KB |
testcase_34 | AC | 2 ms
6,940 KB |
testcase_35 | AC | 2 ms
6,940 KB |
testcase_36 | AC | 2 ms
6,944 KB |
testcase_37 | AC | 1 ms
6,940 KB |
testcase_38 | AC | 1 ms
6,944 KB |
testcase_39 | AC | 2 ms
6,940 KB |
testcase_40 | AC | 2 ms
6,940 KB |
testcase_41 | AC | 2 ms
6,940 KB |
testcase_42 | AC | 2 ms
6,940 KB |
testcase_43 | AC | 2 ms
6,944 KB |
testcase_44 | AC | 1 ms
6,944 KB |
testcase_45 | AC | 1 ms
6,940 KB |
testcase_46 | AC | 2 ms
6,940 KB |
testcase_47 | AC | 2 ms
6,940 KB |
testcase_48 | AC | 2 ms
6,944 KB |
testcase_49 | AC | 2 ms
6,944 KB |
testcase_50 | AC | 2 ms
6,940 KB |
testcase_51 | AC | 2 ms
6,940 KB |
testcase_52 | AC | 2 ms
6,944 KB |
testcase_53 | AC | 2 ms
6,944 KB |
testcase_54 | AC | 2 ms
6,940 KB |
testcase_55 | AC | 1 ms
6,940 KB |
testcase_56 | AC | 2 ms
6,940 KB |
testcase_57 | AC | 2 ms
6,940 KB |
testcase_58 | AC | 2 ms
6,944 KB |
testcase_59 | AC | 1 ms
6,944 KB |
testcase_60 | AC | 1 ms
6,944 KB |
testcase_61 | AC | 1 ms
6,940 KB |
testcase_62 | AC | 2 ms
6,940 KB |
testcase_63 | AC | 2 ms
6,940 KB |
testcase_64 | AC | 2 ms
6,940 KB |
testcase_65 | AC | 2 ms
6,944 KB |
testcase_66 | AC | 2 ms
6,940 KB |
testcase_67 | AC | 2 ms
6,944 KB |
testcase_68 | AC | 2 ms
6,940 KB |
testcase_69 | AC | 2 ms
6,940 KB |
testcase_70 | AC | 1 ms
6,944 KB |
testcase_71 | AC | 1 ms
6,940 KB |
testcase_72 | AC | 1 ms
6,944 KB |
testcase_73 | AC | 2 ms
6,940 KB |
testcase_74 | AC | 2 ms
6,940 KB |
testcase_75 | AC | 2 ms
6,940 KB |
testcase_76 | AC | 2 ms
6,940 KB |
testcase_77 | AC | 2 ms
6,940 KB |
testcase_78 | AC | 2 ms
6,944 KB |
testcase_79 | AC | 1 ms
6,940 KB |
ソースコード
#include <bits/stdc++.h> #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") using namespace std; //-------------------------------------------------------------------- #define all(a) (a).begin(),(a).end() #define rall(a) (a).rbegin(),(a).rend() #define overload4(_1,_2,_3,_4,name,...) name #define rep1(n) for(ll _=0;_<(ll)n;++_) #define rep2(i,n) for(ll i=0;i<(ll)n;++i) #define rep3(i,a,b) for(ll i=(ll)a;i<(ll)b;++i) #define rep4(i,a,b,c) for(ll i=(ll)a;i<(ll)b;i+=(ll)c) #define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__) #ifdef _DEBUG #define pass(...) __VA_ARGS__ ; #define debug1(a) cerr<<#a<<": "<<a<<"\n" #define debug2(a,b) cerr<<#a<<": "<<a<<", "<<#b<<": "<<b<<"\n" #define debug3(a,b,c) cerr<<#a<<": "<<a<<", "<<#b<<": "<<b<<", "<<#c<<": "<<c<<"\n" #define debug4(a,b,c,d) cerr<<#a<<": "<<a<<", "<<#b<<": "<<b<<", "<<#c<<": "<<c<<", "<<#d<<": "<<d<<"\n" /* #define debug1(a) cout<<#a<<": "<<a<<"\n" #define debug2(a,b) cout<<#a<<": "<<a<<", "<<#b<<": "<<b<<"\n" #define debug3(a,b,c) cout<<#a<<": "<<a<<", "<<#b<<": "<<b<<", "<<#c<<": "<<c<<"\n" #define debug4(a,b,c,d) cout<<#a<<": "<<a<<", "<<#b<<": "<<b<<", "<<#c<<": "<<c<<", "<<#d<<": "<<d<<"\n" */ #define debug(...) overload4(__VA_ARGS__,debug4,debug3,debug2,debug1)(__VA_ARGS__) #define koko cerr << "koko\n"; #else #define debug(...) void(0) #define pass(...) void(0); #define koko void(0); #endif #define mp make_pair //#define fi first //#define se second void myset(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);} void doset(int n){cout << fixed << setprecision(n);cerr << fixed << setprecision(n);} using ll = long long; using ld = long double; using dou = double; template<class First,class Second>ostream& operator<<(ostream& os,const pair<First,Second>& pp) {return os << "{" << pp.first << "," << pp.second << "}";} template<class T>ostream& operator<<(ostream& os,const vector<T>& VV) {if(VV.empty())return os<<"[]";os<<"[";rep(i,VV.size())os<<VV[i]<<(i==int(VV.size()-1)?"]":",");return os;} template<class T>ostream& operator<<(ostream& os,const set<T>& SS) {if(SS.empty())return os<<"[]";os<<"[";auto ii=SS.begin();for(;ii!=SS.end();ii++)os<<*ii<<(ii==prev(SS.end())?"]":",");return os;} template<class Key,class Tp>ostream& operator<<(ostream& os,const map<Key,Tp>& MM) {if(MM.empty())return os<<"[]";os<<"[";auto ii=MM.begin();for(;ii!=MM.end();ii++)os<<"{"<<ii->first<<":"<<ii->second<<"}"<<(ii==prev(MM.end())?"]":",");return os;} const int inf = 1 << 30; const ll INF = 1LL << 61; const ld pi = 3.14159265358; const ll mod1 = 1000000007LL; const ll mod2 = 998244353LL; typedef pair<ll,ll> P; template<class T, class U> inline bool chmin(T& a, const U& b){ if(a > b){ a = b; return 1; } return 0; } template<class T, class U> inline bool chmax(T& a, const U& b){ if(a < b){ a = b; return 1; } return 0; } ll modpow(ll n,ll m,ll MOD){ if(m == 0)return 1; if(m < 0)return 0; ll res = 1; n %= MOD; while(m){ if(m & 1)res = (res * n) % MOD; m >>= 1; n *= n; n %= MOD; } return res; } ll mypow(ll n,ll m){ if(m == 0)return 1; if(m < 0)return -1; ll res = 1; while(m){ if(m & 1)res = (res * n); m >>= 1; n *= n; } return res; } inline bool isp(ll n){ bool res = true; if(n == 1 || n == 0)return false; else{ for(ll i = 2;i * i <= n;i++){ if(n % i == 0){ res = false; break; } } return res; } } inline bool Yes(bool b = 1){cout << (b ? "Yes\n":"No\n");return b;} inline bool YES(bool b = 1){cout << (b ? "YES\n":"NO\n");return b;} map<ll,ll> primefactor(ll n){ map<ll,ll> ma; if(n <= 1)return ma; ll m = n; for(ll i = 2;i * i <= n;i++){ while(m % i == 0){ ma[i]++; m /= i; } } if(m != 1)ma[m]++; return ma; } vector<ll> divisor(ll n,bool sorted = true,bool samein = false){ vector<ll> res; for(ll i = 1;i * i <= n;i++){ if(n % i == 0){ res.push_back(i); if(i * i != n || samein)res.push_back(n / i); } } if(sorted)sort(all(res)); return res; } ll __lcm(ll a,ll b){return a / __gcd(a,b) * b;} template<class T>T sum(const vector<T> &V){T r=0;for(auto x:V)r+=x;return r;} template<class T>T sum(const initializer_list<T> &V){T r=0;for(auto x:V)r+=x;return r;} //-------------------------------------------------------------------- using e_t = long long; std::vector<std::vector<e_t>> warshal_floid(const std::vector<std::vector<e_t>> &G,e_t LM = std::numeric_limits<e_t>::max()){ std::vector<std::vector<e_t>> res = G; int n = res.size(); for(int i = 0;i < n;i++){ for(int j = 0;j < n;j++){ for(int k = 0;k < n;k++){ if(res[j][i] == LM || res[i][k] == LM)continue; else if(res[j][k] > res[j][i] + res[i][k])res[j][k] = res[j][i] + res[i][k]; } } } return res; } int main(){ myset(); int N,M; cin >> N >> M; vector<vector<e_t>> G(N,vector<e_t>(N,INF)); rep(i,M){ int a,b;ll c; cin >> a >> b >> c; a--;b--; G[a][b] = min(G[a][b],c); } auto ans = warshal_floid(G,INF); rep(i,N){ e_t cur = 0; rep(j,N)if(i != j)cur += ans[i][j] == INF ? 0 : ans[i][j]; cout << cur << "\n"; } }