poj1502 spfa最短路

 //Accepted    320 KB    16 ms
 //有n个顶点,边权用A表示
 //给出下三角矩阵,求从一号顶点出发到各点的最短路的最大值
 #include <cstdio>
 #include <cstring>
 #include <iostream>
 #include <queue>
 #include <cmath>
 #include <algorithm>
 using namespace std;
 /**
   * This is a documentation comment block
   * 如果有一天你坚持不下去了,就想想你为什么走到这儿!
   * @authr songt
   */
 ;
 const int imax_e = imax_n*imax_n;
 ;
 struct node
 {
     int u,v,c;
     node(,,):u(u),v(v),c(c)
     {

     }
 }p[imax_e];
 int head[imax_n];
 int next[imax_e];
 bool vis[imax_n];
 int dis[imax_n];
 int cnt[imax_n];
 int n;
 ;
 void init()
 {
     memset(head,-,sizeof(head));
     memset(next,-,sizeof(next));
     e=;
 }
 void addEdge(int u,int v,int c)
 {
     p[e]=node(u,v,c);
     next[e]=head[u];
     head[u]=e++;
 }
 bool relax(int u,int v,int c)
 {
     if (dis[v]>dis[u]+c)
     {
         dis[v]=dis[u]+c;
         return true;
     }
     return false;
 }
 queue<int > q;
 bool spfa(int src)
 {
     while (!q.empty()) q.pop();
     memset(vis,,sizeof(vis));
     memset(cnt,,sizeof(cnt));
     ;i<=n;i++)
     dis[i]=inf;
     dis[src]=;
     q.push(src);
     vis[src]=;
     cnt[src]++;
     while (!q.empty())
     {
         int pre=q.front();
         q.pop();
         vis[pre]=;
         ;i=next[i])
         {
             if (relax(pre,p[i].v,p[i].c) && !vis[p[i].v])
             {
                 if ((++cnt[p[i].v])>=n) return false;
                 vis[p[i].v]=;
                 q.push(p[i].v);
             }
         }
     }
     return true;
 }
 ];
 int main()
 {
     while (scanf("%d",&n)!=EOF)
     {
         init();
         ;i<=n;i++)
         {
             ;j<i;j++)
             {
                 scanf("%s",s);
                 ]=='x') continue;
                 int c=atoi(s);
                 //printf("c=%d\n",c);
                 addEdge(i,j,c);
                 addEdge(j,i,c);
             }
         }
         spfa();
         ;
         ;i<=n;i++)
         if (dis[i]>ans) ans=dis[i];
         printf("%d\n",ans);
     }
     ;
 }
上一篇:VS2012中丢失ArcGIS模板的解决方法


下一篇:Sagit.Framework For IOS 开发框架入门教程4:注册页布局-被消灭的变量