poj2263-白红宇

poj2263

阅读量：5922 次

发布时间：2019-06-19

本文共 1897 字，大约阅读时间需要 6 分钟。

最短路

map如果要使用char*作为key，不能简单的直接使用，可以用string作为map的key，使用的时候将char*转换为string。转换的方法是使用string的assign函数。string.assign(char*);

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           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
            
              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 #%d\n%d tons\n\n", t, dijkstra(start_pos, end_pos)); } return 0;}