結果

提出番号	9
提出者	olphe
言語	C++
提出日時	2017-05-20 23:52:24
問題名	(2)Taxis
結果	TLE
点数	80%

---

テストケース

ソースコード

#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "math.h"
#include "utility"
#include "string"
#include "map"
#include "unordered_map"
#include "iomanip"
#include "random"
 
using namespace std;
const long long int MOD = 1000000007;
 
int N, K;
list<int>edge[5000];
list<int>can;
queue<int>box;
priority_queue<long long int, vector<long long int>, greater<long long int>>Q;
 
int main() {
    ios::sync_with_stdio(false);
    cin >> N >> K;
    vector<int>cost(N);
    vector<int>far(N);
    vector<int>dis(N, INT_MAX);
    dis[0] = 0;
    for (int i = 0; i < N; i++)cin >> cost[i] >> far[i];
    for (int i = 0; i < K; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    vector<int>move(N, INT_MAX);
    Q.push(0);
    while (!Q.empty()) {
        int current = Q.top() % MOD;
        int dist = Q.top() / MOD;
        box.push(current);
        for (int i = 0; i < N; i++)move[i] = INT_MAX;
        move[current] = 0;
        while (!box.empty()) {
            for (auto j : edge[box.front()]) {
                if (move[j] > move[box.front()] + 1) {
                    move[j] = move[box.front()] + 1;
                    box.push(j);
                }
            }
            box.pop();
        }
        for (int j = 0; j < N; j++) {
            if (move[j] && move[j] <= far[current])can.push_back(j);
        }
        for (auto i : can) {
            if (dis[i] > dist + cost[current]) {
                dis[i] = dist + cost[current];
                Q.push(dis[i] * MOD + i);
            }
        }
        can.clear();
        Q.pop();
    }
    cout << dis[N - 1] << endl;
    return 0;
}