记录编号	41631	评测结果	AA
题目名称	[咲 -Saki-] 一起进军全国吧	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2012-08-05 16:21:09	内存使用	3.46 MiB

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <vector>
#include <map>
using namespace std;
const int N = 10000 + 10, S = 256;
const int INF = 0x7ffffff;
int n, d, k, m;
char s[S], st[S];
string ss;
double p, w, f[N];
map<string, int> a;
map<string, int>::iterator it;
vector<int> G[N];
vector<double> c[N];
priority_queue<pair<double, int> > q;
bool l[N];
void Dijkstra() {
    memset(l, 0, sizeof(l));
    for(int i=0; i<=m; i++) f[i] = INF;
    f[0] = 0;
    q.push(make_pair(-f[0], 0));
    while(!q.empty()) {
        int u = q.top().second; q.pop();
        if(!l[u]) {
            l[u] = 1;
            for(int i=0; i<G[u].size(); i++) {
                int v = G[u][i];
                if(!l[v] && f[v] > f[u] + c[u][i]) {
                    f[v] = f[u] + c[u][i];
                    q.push(make_pair(-f[v], v));
                }
            }
        }
    }
}
int main() {
    freopen("zengokuhe.in", "r", stdin);
    freopen("zengokuhe.out", "w", stdout);
    scanf("%d %s\n", &n, s);
    a[ss = s] = m = 0;
    for(int i=0; i<n; i++) {
        scanf("%s\n", s);
        a[ss = s] = ++m;
    }
    int u, v;
    while(fgets(s, S, stdin)) {
        if(s[0] == 'S')
            k = 0;
        else {
            if(s[0] >= '0' && s[0] <= '9')
                sscanf(s, "%lf %s", &w, st);
            else
                sscanf(s, "%s %lf", st, &w);
            ss = st;
            if((it = a.find(ss)) == a.end())
                a[ss] = v = ++m;
            else
                v = it->second;
            if(k) {
                G[u].push_back(v); c[u].push_back(fabs(w-p));
                G[v].push_back(u); c[v].push_back(fabs(w-p));
            } k++;
            u = v, p = w;
        }
    }
    /*for(it=a.begin(); it!=a.end(); it++)
        fprintf(stderr, "%d %s\n", it->second, it->first.c_str());*/
    /*for(int i=0; i<=m; i++) {
        fprintf(stderr, "%d: ", i);
        for(int j=0; j<G[i].size(); j++)
            fprintf(stderr, "(%d, %.2lf) ", G[i][j], c[i][j]);
        fprintf(stderr, "\n");
    }*/
    Dijkstra();
    for(int i=1; i<=n; i++)
        printf("%.2lf\n", f[i] >= INF ? -1 : f[i]);
    return 0;
}