MPI Maelstrom POJ - 1502-白红宇

MPI Maelstrom POJ - 1502

阅读量：280 次

发布时间：2019-03-01

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

题意：大致意思是1到其他点的最短距离中最大的那个距离是多少。

可以用的算法：Floyd，Dijkstar，Bellman-Ford，Spfa

~~个人这道题用了Spfa，因为上道题用了Spfa，不想重写了，嘿嘿嘿~~

#include
   
    #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 <= n; 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;}