結果

問題 No.1602 With Animals into Institute 2
コンテスト
ユーザー cureskol
提出日時 2021-07-12 19:17:26
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,500 bytes
コンパイル時間 2,666 ms
コンパイル使用メモリ 193,888 KB
実行使用メモリ 31,284 KB
最終ジャッジ日時 2024-07-02 03:33:49
合計ジャッジ時間 8,743 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 9 WA * 18 RE * 9
権限があれば一括ダウンロードができます

ソースコード

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();
  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