結果

問題 No.1602 With Animals into Institute 2
ユーザー cureskolcureskol
提出日時 2021-07-12 19:18:06
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,502 bytes
コンパイル時間 2,133 ms
コンパイル使用メモリ 192,860 KB
実行使用メモリ 32,776 KB
最終ジャッジ日時 2023-09-14 20:43:18
合計ジャッジ時間 9,017 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 AC 9 ms
4,376 KB
testcase_05 WA -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 AC 1 ms
4,376 KB
testcase_28 AC 1 ms
4,380 KB
testcase_29 AC 2 ms
4,376 KB
testcase_30 AC 2 ms
4,376 KB
testcase_31 AC 2 ms
4,380 KB
testcase_32 AC 1 ms
4,380 KB
testcase_33 WA -
testcase_34 WA -
testcase_35 AC 2 ms
4,376 KB
testcase_36 AC 1 ms
4,376 KB
testcase_37 AC 1 ms
4,376 KB
testcase_38 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i=0;i<n;i++)
using ll=long long;

struct DisjointTree{
  int n;
  vector<int> r,p;
  DisjointTree(int n):n(n),p(n,0){iota(p.begin(),p.end(),0);}
  int find(int x){
    return (x==p[x]?x:p[x]=find(p[x]));
  }
};

template <typename A,typename I>
struct FastUp{
  struct E{
    int from,to;
    I c;
    A a;
    bool operator <(const E &tmp)const{
      return true;
    };
  };
  struct Spt{
    I dist;
    int pred;
    A sum;
  };
  typedef pair<I,int> P;
  typedef pair<I,E> IE;
  using F=function<A(A,A)>;//群の演算の型
  F f;//演算
  A ti;//単位元
  vector<vector<E>> G;
  const I INF=numeric_limits<I>::max()/3;
  int s,n;

  FastUp(){}
  FastUp(vector<vector<E>> G,int s,F f,A ti):G(G),s(s),f(f),ti(ti){
    n=G.size();
  }

  inline vector<Spt> dijkstra(){
    vector<Spt> d(n,{INF,-1,ti});
    d[s].dist=0;
    priority_queue<P,vector<P>,greater<P>> que;
    que.push(P(0,s));
    while(que.size()){
      P tmp=que.top();que.pop();
      I dist=tmp.first;
      int idx=tmp.second;
      if(d[idx].dist<dist)continue;
      for(E p:G[idx])
        if(d[p.to].dist>dist+p.c){
          d[p.to]={dist+p.c,idx,f(d[idx].sum,p.a)};
          que.push(P(d[p.to].dist,p.to));
        }
    }
    return d;
  }

  vector<I> solve(){
    vector<I> res(n,INF);
    DisjointTree dt(n);
    priority_queue<IE,vector<IE>,greater<IE>> que;
    auto T=dijkstra();
    for(int i=0;i<n;i++)if(T[i].sum!=ti)res[i]=T[i].dist;
    for(int i=0;i<n;i++)for(E e:G[i])
      if(f(T[i].sum,e.a)!=T[e.to].sum)que.push(IE(T[i].dist+T[e.to].dist+e.c,e));
    while(que.size()){
      IE p=que.top();que.pop();
      int w1=dt.find(p.second.from),w2=dt.find(p.second.to);
      stack<int> B;
      while(w1!=w2){
        if(T[w1].dist<T[w2].dist)swap(w1,w2);
        B.push(w1);
        w1=dt.find(T[w1].pred);
      }
      while(B.size()){
        int v=B.top();B.pop();
        dt.p[v]=w1;
        res[v]=min(res[v],p.first-T[v].dist);
        for(E e:G[v])if(f(T[v].sum,e.a)==T[e.to].sum)que.push(IE(res[v]+T[e.to].dist+e.c,e));
      }
    }
    return res;
  }
};


int main(){
  int n,m,k;cin>>n>>m>>k;
  FastUp<int,ll> F;
  F.G.resize(n);
  F.n=n;
  F.f=[](int a,int b){return a^b;};
  F.ti=0;
  F.s=n-1;
  REP(_,m){
    int u,v,c,x;cin>>u>>v>>c>>x;u--;v--;
    F.G[u].push_back({u,v,c,x});
    F.G[v].push_back({v,u,c,x});
  }
  auto ans=F.solve();
  REP(i,n-1)
    if(ans[i]>1e17)cout<<-1<<endl;
    else cout<<ans[i]<<endl;
}
0