結果

問題 No.1344 Typical Shortest Path Sum
ユーザー αmusement
提出日時 2021-01-16 13:14:14
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,710 bytes
コンパイル時間 16,053 ms
コンパイル使用メモリ 288,360 KB
最終ジャッジ日時 2025-01-17 21:47:09
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 72 TLE * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

//#pragma GCC target("avx512f,avx512dq,avx512cd,avx512bw,avx512vl")
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define DB double
#define LD long double
#define ST string
#define BS bitset
#define PA pair<LL,LL>
#define VE vector
#define VL VE<LL>
#define VP VE<PA>
#define VVL VE<VL>
#define VVVL VE<VVL>
#define PQ priority_queue
#define PQS priority_queue<LL,vector<LL>,greater<LL>>
#define FI first
#define SE second
#define PB push_back
#define POB pop_back
#define PF push_front
#define POF pop_front
#define MP make_pair
#define TS to_string
#define TU to_ullong
#define BPL __builtin_popcountll
#define FOR(i,a,n) for(i=a;i<n;++i)
#define FORR(i,a,n) for(i=n-1;i>=a;--i)
#define rep(i,n) FOR(i,0,n)
#define repr(i,n) FORR(i,0,n)
#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()
#define SORT(a) sort(ALL(a))
#define REV(a) reverse(ALL(a))
#define UB(a,n) *upper_bound(ALL(a),n)
#define UBn(a,n) upper_bound(ALL(a),n)-a.begin()
#define LB(a,n) *lower_bound(ALL(a),n)
#define LBn(a,n) lower_bound(ALL(a),n)-a.begin()
#define INF 1000000000000000003
#define PI 3.14159265358979323846264338327950288
#define MOD 1000000007
//#define MOD 998244353
#define ERR 1e-10
#define coutl cout<<fixed<<setprecision(15)
#define FAST cin.tie(0);ios::sync_with_stdio(false)

void Yn(LL a){if(a)printf("Yes\n");else printf("No\n");}
void YN(LL a){if(a)printf("YES\n");else printf("NO\n");}
void vout(VL &v){LL i;rep(i,v.size()){printf("%lld",v[i]);if(i<v.size()-1)printf(" ");}printf("\n");}
void v2out(VVL &v){LL i;rep(i,v.size())vout(v[i]);}
LL pwmn(LL a,LL n){LL ans=1;while(ans<a)ans*=n;return ans;}
LL dig(LL n){LL ret=0;while(n)n/=10,++ret;return ret;}
LL GCD(LL a,LL b){LL c=1,tmp=max(a,b);b=min(a,b);a=tmp;while(c!=0){c=a%b;a=b;b=c;}return a;}
LL LCM(LL a,LL b){return a*b/GCD(a,b);}
LL cmod(LL a,LL m){if(a%m<0)return a%m+abs(m);else return a%m;}
LL DIV(LL a,LL d,LL m){LL l=m,x=1,y=0,k;while(l){k=d/l;d-=k*l;swap(l,d);x-=k*y;swap(x,y);}return cmod(a*cmod(x,m),m);}
LL POW(LL a,LL n,LL m){LL ans=1;while(n>0){if(n&1)ans=ans*a%m;a=a*a%m;n>>=1;}return ans;}
VL fact,finv,inv;
void comi(LL n){LL i;fact.resize(max(2LL,n+1));finv.resize(max(2LL,n+1));inv.resize(max(2LL,n+1));fact[0]=fact[1]=1;finv[0]=finv[1]=1;inv[1]=1;FOR(i,2,n+1){fact[i]=fact[i-1]*i%MOD;inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;finv[i]=finv[i-1]*inv[i]%MOD;}}
LL com(LL n,LL k){if(n<k||n<0||k<0)return 0;return fact[n]*(finv[k]*finv[n-k]%MOD)%MOD;}
bool cmps(PA a,PA b){if(a.SE!=b.SE)return a.SE<b.SE;return a.FI<b.FI;}
template<typename T>bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<typename T>bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;}

typedef struct{VP t;LL f,c,n;}Node;
struct Dijkstra{
    VE<Node> node;
    Dijkstra(LL n){LL i;node.resize(n);rep(i,n)node[i].n=i,node[i].f=-1,node[i].c=INF;}
    void add(LL s,LL e,LL c){node[s].t.PB({c,e});}
    void run(LL s=0,LL c=0){LL i;PQ<PA,VP,greater<PA>> pq;node[s].c=c;pq.push({c,s});while(!pq.empty()){PA now=pq.top();pq.pop();LL nowc=now.FI,nown=now.SE;if(nowc>node[nown].c)continue;for(auto ne:node[nown].t){LL nec=nowc+ne.FI,nen=ne.SE;if(chmin(node[nen].c,nec))pq.push({nec,nen}),node[nen].f=nown;}}}
};

int main(){
    FAST;
    LL i,j,k,ans=0,N,M;
    cin>>N>>M;
    VL s(M),t(M),d(M);
    rep(i,M){
        cin>>s[i]>>t[i]>>d[i];
        --s[i],--t[i];
    }
    rep(i,N){
        ans=0;
        Dijkstra D(N);
        rep(j,M)D.add(s[j],t[j],d[j]);
        D.run(i);
        rep(j,N){
            //cout<<D.node[j].c<<" ";
            if(D.node[j].c<INF)ans+=D.node[j].c;
        }
        cout<<ans<<endl;
    }
}
0