TLE...

Sphere Online Judgeの15. The Shortest Pathが解けない…

ダイクストラ法で解けると思うんだけど、実際にやってみるとTime Limit Exceededになる。一応メモ化もしてみたけどTLEのまま。なにか見落としてるのかなあ。

諦めたのでコードさらします。

[追記] 諦めきれずにsubmitしつづけていたらacceptされてしまった。
なんかmultimapの代わりにpriority_queueを使えばあっさり通った。なんじゃそりゃ。
あと、結局メモ化しないほうが速かったorz

TLEなコード

#include <stdio.h>
#include <string.h>
#include <vector>
#include <map>
using namespace std;

struct City {
    vector<int> neighbour_indexes;
    vector<int> neighbour_costs;
    char name[11];
    int cost;
    bool done;
};

City cities[10000];
short memo[10000][10000];
multimap<int, int> queue;

int main()
{
    int s, n, p, r, nr, cost, from, to;
    char from_str[11], to_str[11];

    scanf("%d", &s);
    while (s--) {
        scanf("%d", &n);
        for (int i = 0; i < n; ++i) {
            City& city = cities[i];
            city.neighbour_indexes.clear();
            city.neighbour_costs.clear();
            scanf("%s", city.name);
            scanf("%d", &p);
            while (p--) {
                scanf("%d %d", &nr, &cost);
                city.neighbour_indexes.push_back(nr - 1);
                city.neighbour_costs.push_back(cost);
            }
        }
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                memo[i][j] = -1;
        scanf("%d", &r);
        while (r--) {
            scanf("%s %s", from_str, to_str);
            for (int i = 0; i < n; ++i) {
                cities[i].cost = 999999999;
                cities[i].done = false;
                if (strcmp(cities[i].name, from_str) == 0)
                    from = i;
                if (strcmp(cities[i].name, to_str) == 0)
                    to = i;
            }
            cities[from].cost = 0;
            queue.clear();
            queue.insert(make_pair(0, from));
            while (!queue.empty()) {
                int city_no = queue.begin()->second;
                City& city = cities[city_no];
                memo[from][city_no] = city.cost;
                if (city_no == to)
                    break;
                queue.erase(queue.begin());
                if (city.done)
                    continue;
                city.done = true;
                int memoized_cost = (memo[city_no][to] & memo[to][city_no]);
                if (memoized_cost >= 0) {
                    int c = city.cost + memoized_cost;
                    if (c < cities[to].cost)
                        cities[to].cost = c;
                    continue;
                }
                int size = city.neighbour_indexes.size();
                for (int i = 0; i < size; ++i) {
                    int neighbour_index = city.neighbour_indexes[i];
                    City& neighbour = cities[neighbour_index];
                    int c = city.cost + city.neighbour_costs[i];
                    if (c < neighbour.cost) {
                        neighbour.cost = c;
                        queue.insert(make_pair(c, neighbour_index));
                    }
                }
            }
            printf("%d\n", cities[to].cost);
//            for (int i = 0; i < n; ++i) {
//                for (int j = 0; j < n; ++j) {
//                    int a = memo[i][j];
//                    if (a >= 0)
//                        printf("%d ", a);
//                    else
//                        printf("- ");
//                }
//                putchar('\n');
//            }
        }
    }
    return 0;
}

[追記] Acceptされたコード

#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;

struct City {
    vector<int> neighbour_indexes;
    vector<int> neighbour_costs;
    char name[11];
    int cost;
    bool done;
};

struct Item {
    int cost;
    int city_no;
    Item(int cost, int city_no): cost(cost), city_no(city_no) {}
    bool operator<(const Item& rhs) const { return cost > rhs.cost; }
};

City cities[10000];
//short memo[10000][10000];

int main()
{
    int s, n, p, r, nr, cost, from, to;
    char from_str[11], to_str[11];

    scanf("%d", &s);
    while (s--) {
        scanf("%d", &n);
        for (int i = 0; i < n; ++i) {
            City& city = cities[i];
            city.neighbour_indexes.clear();
            city.neighbour_costs.clear();
            scanf("%s", city.name);
            scanf("%d", &p);
            while (p--) {
                scanf("%d %d", &nr, &cost);
                city.neighbour_indexes.push_back(nr - 1);
                city.neighbour_costs.push_back(cost);
            }
        }
//        for (int i = 0; i < n; ++i)
//            for (int j = 0; j < n; ++j)
//                memo[i][j] = -1;
        scanf("%d", &r);
        while (r--) {
            scanf("%s %s", from_str, to_str);
            for (int i = 0; i < n; ++i) {
                cities[i].cost = 999999999;
                cities[i].done = false;
                if (strcmp(cities[i].name, from_str) == 0)
                    from = i;
                if (strcmp(cities[i].name, to_str) == 0)
                    to = i;
            }
            cities[from].cost = 0;
            priority_queue<Item> Q;
            Q.push(Item(0, from));
            while (!Q.empty()) {
                int city_no = Q.top().city_no;
                City& city = cities[city_no];
//                memo[from][city_no] = city.cost;
                if (city_no == to)
                    break;
                Q.pop();
                if (city.done)
                    continue;
                city.done = true;
//                int memoized_cost = (memo[city_no][to] & memo[to][city_no]);
//                if (memoized_cost >= 0) {
//                    int c = city.cost + memoized_cost;
//                    if (c < cities[to].cost)
//                        cities[to].cost = c;
//                    continue;
//                }
                int size = city.neighbour_indexes.size();
                for (int i = 0; i < size; ++i) {
                    int neighbour_index = city.neighbour_indexes[i];
                    City& neighbour = cities[neighbour_index];
                    int c = city.cost + city.neighbour_costs[i];
                    if (c < neighbour.cost) {
                        neighbour.cost = c;
                        Q.push(Item(c, neighbour_index));
                    }
                }
            }
            printf("%d\n", cities[to].cost);
//            for (int i = 0; i < n; ++i) {
//                for (int j = 0; j < n; ++j) {
//                    int a = memo[i][j];
//                    if (a >= 0)
//                        printf("%d ", a);
//                    else
//                        printf("- ");
//                }
//                putchar('\n');
//            }
        }
    }
    return 0;
}