poj 2263 Heavy Cargo

poj 2263 Heavy Cargo

#include <iostream>#include <cstdlib>#include <cstdio>#include <cstring>#include <algorithm>#include <map>using namespace std;#define maxn 205#define maxm 20005#define maxl 50struct Edge{    int v, w, next;}edge[maxm * 2];int city_num, road_num;int head[maxn];map<string, int> city_name;int city_cnt;int edge_cnt;int start_pos, end_pos;int dist[maxn];bool vis[maxn];void addedge(int a, int b, int weight){    edge[edge_cnt].v = b;    edge[edge_cnt].w = weight;    edge[edge_cnt].next = head[a];    head[a] = edge_cnt++;}int city_id(char *st){    string a;    a.assign(st);    if (city_name.find(a) == city_name.end())    {        city_name[a] = city_cnt++;        return city_cnt - 1;    }    return city_name[a];}void input(){    memset(head, -1, sizeof(head));    edge_cnt = 0;    city_cnt = 0;    city_name.clear();    char a[maxl], b[maxl];    int weight;    for (int i = 0; i < road_num; i++)    {        scanf("%s%s%d", a, b, &weight);        int id_a = city_id(a);        int id_b = city_id(b);        addedge(id_a, id_b, weight);        addedge(id_b, id_a, weight);    }    scanf("%s%s", a, b);    start_pos = city_id(a);    end_pos = city_id(b);}int dijkstra(int s, int e){    memset(vis, 0, sizeof(vis));    memset(dist, 0, sizeof(dist));    dist[s] = 10000;    while (1)    {        int p = -1;        int temp = -1;        for (int i = 0; i < city_num; i++) if (!vis[i] && dist[i] > temp) {     p = i;     temp = dist[i]; }        if (p == -1) break;        vis[p] = true;        for (int i = head[p]; i != -1; i = edge[i].next) dist[edge[i].v] = max(dist[edge[i].v], min(dist[p], edge[i].w));    }    return dist[e];}int main(){    int t = 0;    while (scanf("%d%d", &city_num, &road_num), city_num | road_num)    {        t++;        input();        printf("Scenario #%dn%d tonsnn", t, dijkstra(start_pos, end_pos));    }    return 0;}