Submission #00117

ソースコード

#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <functional>
using namespace std;
 
using ll = long long int;
 
struct edge {
        edge(int a, int b) :to(a), cost(b) {};
        int to, cost;
};
 
bool operator< (const edge &student1, const edge &student2) {
        return student1.cost < student2.cost;
};
 
bool operator> (const edge &student1, const edge &student2) {
        return student1.cost > student2.cost;
};
 
using P = pair<ll, ll>;
 
vector<edge> G[1000010];
 
ll d[1000010];
 
ll n, m, X;
 
void solve(int s) {
        priority_queue<P, vector<P>, greater<P>> que;
 
        fill(d, d + n + 1, 100000000);
 
        d[s] = 0;
 
        que.push(P(0, s));
 
        while (!que.empty()) {
                P p = que.top(); que.pop();
                int v = p.second;
                if (d[v] < p.first) continue;
                for (int i = 0; i < G[v].size(); i++) {
                        edge e = G[v][i];
                        if (d[e.to] > d[v] + e.cost) {
                                d[e.to] = d[v] + e.cost;
                                que.push(P(d[e.to], e.to));
                        }
                }
        }
}
 
 
 
int main(void) {
 
        cin >> n >> m >> X;
 
        for (int i = 0; i < m; i++) {
                ll s, t, x;
                cin >> s >> t >> x;
                s--;
                t--;
                G[s].push_back(edge(t, x));
                G[t].push_back(edge(s, x));
        }
 
        solve(0);
 
        if (d[n - 1] * 2 > X) {
                cout << "sleep" << endl;
        }
        else {
                cout << d[n - 1]*2 << endl;
        }
 
}

ステータス

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

セット

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

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
1.in	AC	26 ms	25568 KB	1
2.in	AC	28 ms	25524 KB	1
3.in	AC	19 ms	25608 KB	1
4.in	AC	28 ms	26028 KB	1
5.in	AC	78 ms	30036 KB	1
6.in	AC	536 ms	59936 KB	1