結果

問題 No.160 最短経路のうち辞書順最小
コンテスト
ユーザー nu50218
提出日時 2018-12-16 13:45:18
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 22 ms / 5,000 ms
コード長 2,842 bytes
コンパイル時間 1,954 ms
コンパイル使用メモリ 192,964 KB
実行使用メモリ 6,604 KB
最終ジャッジ日時 2024-09-25 06:28:27
合計ジャッジ時間 3,284 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define FOR(I,X,Y) for(long long (I)=(X);(I)<(Y);(I)++)
#define REP(I,X,Y) for(long long (I)=(Y)-1;(I)>=(X);(I)--)
#define ALL(X) (X).begin(),(X).end()
#define pb push_back
#define COUNT(V,X) upper_bound((V).begin(),(V).end(),X)-lower_bound((V).begin(),(V).end(),X)
#define debug(x) cerr<<#x<<':'<<x<<endl;
#define DEBUG(v) cerr<<#v<<':';for(auto xXx:v)cerr<<xXx<<' ';cerr<<endl;
#define INF 1000000007
#define LINF 1000000000000000007
#define int long long
#define Yes(X) if(X){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}
#define YES(X) if(X){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
typedef long long ll;
typedef long double ld;
long long dx[] = {1,0,-1,0};
long long dy[] = {0,1,0,-1};
long long dx8[] = {1,1,0,-1,-1,-1,0,1};
long long dy8[] = {0,1,1,1,0,-1,-1,-1};
long long dx9[] = {1,1,0,-1,-1,-1,0,1,0};
long long dy9[] = {0,1,1,1,0,-1,-1,-1,0};

struct Graph{
  long long V;
  long long E;
  //u,v,weight,cap
  vector<tuple<long long,long long,long long,long long>> edges;
  void add(long long u,long long v){edges.push_back(make_tuple(u,v,1,1));}
  void add(long long u,long long v,long long weight){edges.push_back(make_tuple(u,v,weight,1));}
  void add(long long u,long long v,long long weight,long long capacity){edges.push_back(make_tuple(u,v,weight,capacity));}
};

//辞書順最小最短経路を返す
vector<long long> Path(const Graph &G,const long long &start,const long long &goal){
  vector<vector<pair<long long,long long>>> adj(G.V),adj2(G.V);
  for(auto t:G.edges)adj[get<0>(t)].push_back(make_pair(get<1>(t),get<2>(t)));
  for(auto t:G.edges)adj2[get<1>(t)].push_back(make_pair(get<0>(t),get<2>(t)));
  long long dmin[G.V];
  for(long long i = 0;i < G.V;i++)dmin[i] = -1;
  priority_queue<pair<long long,long long>,vector<pair<long long,long long>>,greater<pair<long long,long long>>> pque;
  pque.push(make_pair(0,goal));
  pair<long long,long long> p;
  while(pque.size()){
    p = pque.top();pque.pop();
    if(dmin[p.second] == -1){
      dmin[p.second] = p.first;
      for(auto x:adj[p.second])if(dmin[x.first] == -1)pque.push(make_pair(dmin[p.second]+x.second,x.first));
    }
  }
  long long now = start;
  vector<long long> ans(1,now);
  while(now != goal){
    sort(ALL(adj2[now]));
    for(long long i = 0;i < adj2[now].size();i++){
      pair<long long,long long> p = adj2[now][i];
      if(dmin[now] == dmin[p.first]+p.second){
        ans.push_back(p.first);
        now = p.first;
        break;
      }
    }
  }
  return ans;
}

signed main(){
    Graph G;
    ll N,M,s,g,a,b,c;
    cin >> N >> M >> s >> g;
    G.V = N;
    G.E = 2*M;
    FOR(i,0,M){
        cin >> a >> b >> c;
        G.add(a,b,c);
        G.add(b,a,c);
    }
    vector<ll> ans = Path(G,s,g);
    FOR(i,0,ans.size()-1)cout << ans[i] << ' ';
    cout << ans[ans.size()-1] << endl;
}
0