hdu 2112 HDU Today (最短路)-白红宇

hdu 2112 HDU Today (最短路)

阅读量：7078 次

发布时间：2019-06-28

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

　　就一个普通的最短路，除了用floyd会超时外，要注意起点终点地名相同是一个trick。

代码如下：

#include 
      
       #include 
       #include 
        
         #include 
         
          #include 
          
           using namespace std;map
           
             id;const int INF = 11111111;const int N = 222;int mat[N][N];char s[44], t[44];int q[N << 3];void spfa(int s) { int qh, qt; qh = qt = 0; for (int i = 0; i < N; i++) if (mat[s][i] < INF) q[qt++] = i; while (qh < qt) { int cur = q[qh++]; for (int i = 0; i < N; i++) { if (mat[s][i] > mat[s][cur] + mat[cur][i]) { mat[s][i] = mat[s][cur] + mat[cur][i]; q[qt++] = i; } } }}int main() { int n; while (cin >> n && n >= 0) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) mat[i][j] = INF; mat[i][i] = 0;} id.clear(); int d; scanf("%s%s", s, t); if (!strcmp(s, t)) { for (int i = 0; i < n; i++) scanf("%s%s%d", s, t, &d); cout << '0' << endl; continue; } id[s] = id.size(); id[t] = id.size(); for (int i = 0; i < n; i++) { scanf("%s%s%d", s, t, &d); if (id.find(s) == id.end()) id[s] = id.size(); if (id.find(t) == id.end()) id[t] = id.size(); mat[id[s]][id[t]] = mat[id[t]][id[s]] = d; } spfa(1); if (mat[1][2] >= INF) puts("-1"); else printf("%d\n", mat[1][2]); } return 0;}