2014年广州区域赛k题解

碎碎念

尽力啦

题意

好像是最水的那种最短路把，有点多源最短路的感觉，枚举把哪个人封锁，然后跑一遍spfa就好了。复杂度方面倒是完全应付得来呢。

完整代码

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define MAXN 1005
using namespace std;
int n,m,tem1,tem2,tem3,flag,ans,nums;
int head[MAXN],dis[MAXN],vis[MAXN];
struct edge
{
    int next,to,dis;
}edge[1005];
void addedge(int from,int to,int dis)
{
    edge[++nums].next=head[from];
    edge[nums].to=to;
    edge[nums].dis=dis;
    head[from]=nums;
}
void spfa()
{
    int s=1;
    queue<int>q;
    for(int i=1;i<=n;i++)
    {
        dis[i]=INF;
        vis[i]=0;
}
    q.push(s);dis[s]=0;vis[s]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=edge[i].next)
        {
            int v=edge[i].to;
            if(v==flag)
            {
                continue;
            }
            if(dis[v]>dis[u]+edge[i].dis)
            {
                dis[v]=dis[u]+edge[i].dis;
                if(vis[v]==0)
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    ans=max(ans,dis[n]);
}
int main()
{
   while(scanf("%d %d",&n,&m))
   {
       memset(head,0,sizeof(head));
       memset(dis,0,sizeof(head));
       memset(vis,0,sizeof(head));
       nums=0;
       ans=0;
       if(n==0&&m==0)
       {
           break;
       }
       for(int i=1;i<=m;i++)
       {
           scanf("%d %d %d",&tem1,&tem2,&tem3);
           addedge(tem1,tem2,tem3);
           addedge(tem2,tem1,tem3);
       }
        for(int i=2;i<=n-1;i++)
        {
            flag=i;
            spfa();
        }
        if(ans==INF)
        {
            printf("Inf\n");
        }
        else
        {
            printf("%d\n",ans);
        }
   }
}