2014年广州区域赛k题解

碎碎念

尽力啦

题意

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

完整代码

#include
    
     #define INF 0x3f3f3f3f#define MAXN 1005using 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
     
      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);        }   }}