結果

問題 No.807 umg tours
コンテスト
ユーザー 37zigen
提出日時 2019-03-22 23:42:49
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,553 bytes
コンパイル時間 1,810 ms
コンパイル使用メモリ 167,272 KB
実行使用メモリ 30,804 KB
最終ジャッジ日時 2024-11-23 19:12:32
合計ジャッジ時間 12,387 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

std::vector< std::pair<int,int> > g[100000];
long long dp[2][100000];

struct state{
  int id;
  bool used;
  long long dist;
  
};

bool operator> (const state &state1, const state &state2){
  if(state1.dist==state2.dist){
    return !state1.used;
  }else{
    return state1.dist>state2.dist;
  }
}

int main(){
  
  int N, M;
  std::cin>>N>>M;
  
   for(int i=0;i<M;++i)
     {
       int a,b,c;
       std::cin>>a>>b>>c;
       --a;
       --b;
       g[a].push_back(std::make_pair(b,c));
       g[b].push_back(std::make_pair(a,c));
     }
   
   for(int i=0;i<2;++i)
     {
     for(int j=0;j<N;++j)
       {
	 dp[i][j]=1LL<<60;
       }
     }
   
   dp[0][0]=0;
   
   std::priority_queue<state, std::vector<state>, std::greater<state> > pq;
   
   state src={0,false,0};//id,used,dist
   pq.push(src);
   while(!pq.empty()){
     state s = pq.top();
     pq.pop();
     for(std::pair<int, int> dst:g[s.id])
       {
	 if(!s.used&&dp[1][dst.first]>dp[0][s.id])
	   {
	     dp[1][dst.first]=dp[0][s.id];
	     state add= {dst.first,true,dp[1][dst.first]};
	     pq.push(add);
	   }
	 
	 {
	   int p = s.used?1:0;
	   if(dp[p][dst.first]>dp[p][s.id]+dst.second)
	     {
	       dp[p][dst.first]=dp[p][s.id]+dst.second;
	       state add = {dst.first, s.used, dp[p][dst.first]};
	       pq.push(add);
	     }
	 }
	 
       }
   }

   for(int i=0;i<N;++i)
     {
       dp[1][i]=std::min(dp[1][i],dp[0][i]);
     }
   for(int i=0;i<N;++i)
     {
       std::cout<<dp[0][i]+dp[1][i]<<std::endl;
     }
   
   
   return 0;
}
0