MPI Maelstrom POJ - 1502-白红宇

MPI Maelstrom POJ - 1502

阅读量：280 次

发布时间：2019-03-01

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

??????????????????????1????????????????????Floyd?Dijkstra?Bellman-Ford?Spfa???????Spfa????????Spfa????????????????#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #define ll long long#define PI acos(-1)#define mes(x,y) memset(x,y,sizeof(x))#define lp pair
                   
                    #define FAST_IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)using namespace std;const ll inf = 10000000000000005;ll n, m, i, j, k = 0, t, w, flag, x, y, z, sum;string s1, s2, s;struct node { ll end, len; node(ll x, ll y) : end(x), len(y) {}};vector
                    
                      v;ll dis[110];ll ismove[110];ll StrTurnNum(string s) { sum = 0; ll i = 0; while (i < s.length()) { sum = (ll)(s[i++] - '0') + sum * 10; } return sum;}ll Spfa(ll beginkind) { mes(dis, inf); mes(ismove, 0); queue
                     
                       que; dis[beginkind] = 0; que.push(beginkind); while (!que.empty()) { t = que.front(); que.pop(); ismove[t] = 0; for (i = 0; i < v[t].size(); i++) { if (dis[v[t][i].end] > dis[t] + v[t][i].len) { dis[v[t][i].end] = dis[t] + v[t][i].len; if (ismove[v[t][i].end] == 0) { que.push(v[t][i].end); ismove[v[t][i].end] = 1; } } } } for (i = 2, j = dis[1]; i <= n; i++) { j = max(j, dis[i]); } return j;}int main() { cin >> n; for (i = 2; v.resize(n+1); i++) { for (j = 1; j < i; j++) { cin >> s; if (s == "x") continue; else { v[i].push_back(node(j, StrTurnNum(s))); v[j].push_back(node(i, StrTurnNum(s))); } } } cout << Spfa(1) << endl; return 0;}