Source上げるゾ

5.cpp

#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
#include <queue>

#define INF 0xfffffff

using namespace std;

class vertex {
public:
    vector<int> children;
    int plice;
};

int n, k;
int times[5000];
vertex towns[5000];
vector<int> linked[5000];
int dp[5000];

void make_map(int t) {
    int i;
    int has_reached[5000];
    queue<pair<int, int> > q;

    for (i=0;i<n;i++) has_reached[i] = 0;

    q.push(make_pair(t, times[t]));
    while (!q.empty()) {
        pair<int, int> tmp = q.front();q.pop();

        int pos = tmp.first;
        int z = tmp.second;

        if (has_reached[pos]) continue;
        has_reached[pos] = 1;

        if (pos != t) {
            towns[t].children.push_back(pos);
        }

        if (z == 0) continue;

        vector<int>::iterator it = linked[pos].begin();
        while (it != linked[pos].end()) {
            q.push(make_pair(*it, z-1));
            it++;
        }
    }
}

void dijkstra(int t) {
    int i;
    priority_queue<pair<int,int> , vector<pair<int,int> >, greater<pair<int,int> > > q;

    for (i=0;i<n;i++) dp[i] = INF;

    dp[t] = 0;

    q.push(make_pair(t, 0));
    while (!q.empty()) {
        pair<int, int> tmp = q.top();q.pop();
        
        int edge = tmp.first;
        int cost = tmp.second;

        if (cost > dp[edge]) continue;

        vector<int>::iterator it = towns[edge].children.begin();
        while (it != towns[edge].children.end()) {
            int to = *it;

            if (dp[to] > dp[edge] + towns[edge].plice) {
                dp[to] = dp[edge] + towns[edge].plice;
                q.push(make_pair(to, dp[to]));
            }
            it++;
        }
    }
}

        

int main() {
    int i;

    scanf("%d %d", &n, &k);
    for (i=0;i<n;i++) {
        int c, r;

        scanf("%d %d", &c, &r);
        towns[i].plice = c;
        times[i] = r;
    }

    for (i=0;i<k;i++) {
        int a, b;

        scanf("%d %d", &a, &b);
        a--;
        b--;
        linked[a].push_back(b);
        linked[b].push_back(a);
    }

    for (i=0;i<n;i++) {
        make_map(i);
    }

    dijkstra(0);
    printf("%d\n", dp[n-1]);
}