学步园

小记：这题完全是为了练习stl的，毕竟解法有很多，做的过程中，确实发现我的stl能力以及对平台的了解确实很不到位，wa了N次。

思路：我写的代码是spfa+map+vector

spfa来寻找最短路， map来对字符串打上标记，vector来当邻接表。用以加速spfa。虽然我当初是觉得自己写个前向星也是可以的。当时纯当练stl了。

这题也可以用dijsktra来找最短路，trie树来hash，邻接表的话自己可以随便选，数组的邻接表当然更快些。 所以前向星是个不错的选择。

因为dijsktra写的比较多，而spfa很久没写了，于是就用了spfa。

之前用scanf输入字符串，定义是 char str[MAX_]; string s1;  scanf读站名到str里， 然后我直接赋给s1的，因为用的是map。即s1 = str;

这样我的codeblocks 是没报错或者警告的，而hdu的平台也没报错，但是TLE。 应该是很花时间的，交的c++的。所以改了用cin读入。

而且这里也出了wa，我没include<string>,  但是我定义string s1; 也没报错，codeblocks全自动添加的。。。。 然后提交上去就CE

然后g++ TLE，  c++ 1670+ms 过的。

代码：

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <string>

using namespace std;

#define mst(a,b) memset(a,b,sizeof(a))
#define REP(a,b,c) for(int a = b; a < c; ++a)
#define eps 10e-8

const int MAX_ = 155;
const int N = 100010;
const int INF = 0x7fffffff;

int n;

struct node{
    int s, t;
};

map<string, int> mp;
vector<node> g[MAX_];

int d[MAX_];
bool vis[MAX_];
int m, cnt;

void spfa(int start, int end)
{
    queue<int> q;
    q.push(start);
    REP(i, 0, MAX_){
        vis[i] = 0;
        d[i] = INF;
    }
    vis[start] = 1;
    d[start] = 0;

    while(!q.empty()){
        int cur = q.front(); q.pop();

        vis[cur] = 0;

        REP(i, 0, g[cur].size()){
            int s, t;
            s = g[cur][i].s;
            t = g[cur][i].t;
            if(d[s] > d[cur] + t){
                d[s] =  d[cur] + t;
                if(!vis[s]){
                    vis[s] = 1;
                    q.push(s);
                }
            }
        }
    }
    if(d[end] >= INF){
            puts("-1");//printf("-1\n");
    }else
        printf("%d\n", d[end]);

    return ;
}


int main(){
	int T, ss, tt;

	while(~scanf("%d", &n)){
	    if(n == -1)break;
        mp.clear();

        REP(i, 0, MAX_){
            g[i].clear();
        }
        cnt = 1;

        string s1,s2;
        cin>>s1>>s2;
        /*
        if(s1.compare(s2) == 0 ){
            printf("0\n");continue;
        }
        else if(n == 0){
            printf("-1\n");continue;
        }
        */
        ss = mp[s1] = cnt++;
        
        if(mp[s2] == 0)
            mp[s2] = cnt++;
        tt = mp[s2];
        REP(i, 0, n){

            cin>>s1>>s2>>m;

            int s, t;

            if(mp[s1] == 0){
                mp[s1] = cnt++;
            }
            s = mp[s1];
            if(mp[s2] == 0){
                mp[s2] = cnt++;
            }
            t = mp[s2];
            node tmp;
            tmp.t = m;
            tmp.s = s;
            g[t].push_back(tmp);
            tmp.s = t;
            g[s].push_back(tmp);

        }

        spfa(ss,tt);


	}
	return 0;
}

这和discuss里的那位比较像，但是我已经把我之前的代码改的面目全非了， 本来是有个compare的方法的，目的是去掉起点和终点相同的情况。

但是它给了个OLE, 删掉compare就没了。。。。