HDU-2112-HDU Today

这题的话，坑点挺多的，我也WA了好几次。
首先，对于map，因为是多次使用，所以每次处理完一个图之后就要清空。

其次，就是对于DIjkstra跑图的时候，如果这个图是连通图的话，我们每次选取最小值点是一定可以选到的，但是对于不连通的图，如果任何一个点都不与终点连通，那选取最小值点的时候就一定会选到无穷大点。
所以这时候，如果不对我们之前声明的用来存最小值点标号的变量k赋初值的话，那基本*问是越界的，k里面的数原本基本上都是几十万，所以我就一直越界啦~
要么就把最小值等于无穷的时候，直接跳出，也是可以的，然后再对vis标记，这样跳出就不会越界了。

而且其实cin读入还挺快的，因为用的是string类，所以用cin读入了，其实直接用scanf读入字符串也是可的。如果关闭cin和stdio的同步，这cin读入相当快。

#include <iostream>
#include <cstring>
#include <string>
#include <map>
using namespace std;
const int INF = 1 << 30;
int n,cnt,flag,t;
int w[160][160];
int d[160];
bool vis[160];
map<string, int> name;

void Dijkstra()
{
    memset(vis, false, sizeof(vis));
    for (int i = 1; i <= cnt;i++) {
        d[i] = w[1][i];
    }
    vis[1] = 1;
    d[1] = 0;
    for (int i = 1; i < cnt; i++)
    {
        int m=INF, k=0;
        for (int j = 1; j <= cnt; j++)
        {
            if (!vis[j] &&m>d[j]) {
                m=d[j];
                k = j;
            }
        }
        if (m==INF)
            break;
        vis[k] = 1;
        for (int j = 1; j <= cnt;j++) {
            if (!vis[j]&&d[j]>d[k]+w[k][j]) {
                d[j] = d[k] + w[k][j];
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    while (cin>>n&&n!=-1) {
        if (n==0) {
            cout << -1 << endl;
            continue;
        }
        for (int i = 0; i < 160;i++) {
            for (int j = 0; j < 160;j++) {
                w[i][j] = INF;
            }
        }
        name.clear();
        cnt = 1;
        flag = 0;
        string s, e;
        cin >> s >> e;
        if (s==e)
            flag = 1;
        name[s] = cnt++;
        name[e] = cnt++;
        while (n--) {
            cin >> s >> e >> t;
            if (!name[s])
                name[s] = cnt++;
            if (!name[e])
                name[e] = cnt++;
            if (w[name[s]][name[e]]>t) {
                w[name[s]][name[e]] = t;
                w[name[e]][name[s]] = t;
            }
        }
        if (flag) {
            cout << 0 << endl;
            continue;
        }
        cnt--;
        Dijkstra();
        if (d[2]==INF)
            cout << -1 << endl;
        else
            cout << d[2] << endl;
    }
    return 0;
}