Submission #00022

ソースコード

#include <bits/stdc++.h>
 
using namespace std;
 
struct edge
{
  int to, cost;
};
typedef vector< vector< edge > > Graph;
 
template< typename T = int >
T Dijkstra(Graph &g, int s, int t)
{
  typedef pair< T, int > Pi;
 
  vector< T > min_cost(g.size(), numeric_limits< T >::max());
  priority_queue< Pi, vector< Pi >, greater< Pi > > que;
  que.emplace(0, s);
  min_cost[s] = 0;
  while(!que.empty()) {
    auto p = que.top();
    que.pop();
    if(p.second == t) return (p.first);
    if(p.first > min_cost[p.second]) continue;
    for(auto &e : g[p.second]) {
      if(p.first + e.cost >= min_cost[e.to]) continue;
      min_cost[e.to] = p.first + e.cost;
      que.emplace(min_cost[e.to], e.to);
    }
  }
  return (-1);
}
 
int main()
{
  int N, M, X;
  cin >> N >> M >> X;
  Graph g(N);
  while(M--) {
    int S, T, X;
    cin >> S >> T >> X;
    --S, --T;
    g[S].push_back((edge) {T, X});
    g[T].push_back((edge) {S, X});
  }
  auto get = Dijkstra(g, 0, N - 1) * 2;
  if(get >= X || get < 0) puts("sleep");
  else cout << get << endl;
}

ステータス

項目	データ
問題	0003 - 眠れる獅子の肝試し
ユーザー名	ei1333
投稿日時	2017-05-05 20:11:49
言語	C++11
状態	Accepted
得点	100
ソースコード長	1093 Byte
最大実行時間	577 ms
最大メモリ使用量	54780 KB

セット

	セット	得点	Cases
1	ALL	100 / 100	*

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
1.in	AC	15 ms	480 KB	1
2.in	AC	17 ms	464 KB	1
3.in	AC	20 ms	568 KB	1
4.in	AC	17 ms	1132 KB	1
5.in	AC	80 ms	6508 KB	1
6.in	AC	577 ms	54780 KB	1