hdu 2112 HDU Today (最短路)

Problem - 2112

　　就一个普通的最短路，除了用floyd会超时外，要注意起点终点地名相同是一个trick。

代码如下：

#include <cstdio>
#include <map>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;

map<string, int> id;

const int INF = 11111111;
const int N = 222;
int mat[N][N];
char s[44], t[44];
int q[N << 3];

void spfa(int s) {
    int qh, qt;
    qh = qt = 0;
    for (int i = 0; i < N; i++) if (mat[s][i] < INF) q[qt++] = i;
    while (qh < qt) {
        int cur = q[qh++];
        for (int i = 0; i < N; i++) {
            if (mat[s][i] > mat[s][cur] + mat[cur][i]) {
                mat[s][i] = mat[s][cur] + mat[cur][i];
                q[qt++] = i;
            }
        }
    }
}

int main() {
    int n;
    while (cin >> n && n >= 0) {
        for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) mat[i][j] = INF; mat[i][i] = 0;}
        id.clear();
        int d;
        scanf("%s%s", s, t);
        if (!strcmp(s, t)) {
            for (int i = 0; i < n; i++) scanf("%s%s%d", s, t, &d);
            cout << '0' << endl;
            continue;
        }
        id[s] = id.size();
        id[t] = id.size();
        for (int i = 0; i < n; i++) {
            scanf("%s%s%d", s, t, &d);
            if (id.find(s) == id.end()) id[s] = id.size();
            if (id.find(t) == id.end()) id[t] = id.size();
            mat[id[s]][id[t]] = mat[id[t]][id[s]] = d;
        }
        spfa(1);
        if (mat[1][2] >= INF) puts("-1");
        else printf("%d\n", mat[1][2]);
    }
    return 0;
}

 

——written by Lyon