Lightoj1002 【搜索】

题意：

两两之间的点的花费就是：从A点到B的一条路上某段的最大权值；给一个起点，求到各起点的最小花费。

思路：

一开始的思路：

n不是才500，我先建个图，然后DFS一下，不对，是2500；

如果直接暴搜，肯定T了。因为可能有一个环，然后你不能处理一个节点的向上节点。= =、T在这里，所以每次暴搜就相当于每次暴搜了整幅图；一开始写了一发，还以为再一次深刻理解DFS，然后T的我一脸懵逼，卧槽；不过还是加深了DFS的理解= =、。

①：如果要从DFS角度考虑，可以先求最小生成树，然后在树上DFS，主要是不存在环，比较方便；

②：另外一种就是最短路变形，spfa上直接搞搞就好了（这个还是要看对最短路的松弛熟练了没有）；

思想还是利用队列来操作，避免了重复的判断；

转化最小生成树的代码：

#include<stdio.h>

#include<queue>

#include<string.h>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long LL;

const int INF=0x3f3f3f3f;

const LL mod=1e9+7;

const int N=5e2+10;

struct edge{

    int x,y,w;

};

edge q[20000];

int num;

int pre[N];

bool cmp(edge x,edge y)

{

    return x.w<y.w;

}

struct asd{

    int to;

    int w;

    int next;

};

asd ma[20000];

int head[20000],tol;

int dis[N];

bool vis[N];

int n,m,t;

void add(int a,int b,int c)

{

    ma[tol].to=b;

    ma[tol].w=c;

    ma[tol].next=head[a];

    head[a]=tol++;

}

int Find(int x)

{

    int r=x;

    while(pre[r]!=r)

        r=pre[r];

    int i=x,j;

    while(pre[i]!=r)

    {

        j=pre[i];

        pre[i]=r;

        i=j;

    }

    return r;

}

void init()

{

    sort(q,q+num,cmp);

    for(int i=0;i<n;i++)

        pre[i]=i;

    tol=0;

    memset(head,-1,sizeof(head));

    for(int i=0;i<num;i++)

    {

        int fx=Find(q[i].x);

        int fy=Find(q[i].y);

        if(fx!=fy)

        {

            pre[fx]=fy;

            add(q[i].x,q[i].y,q[i].w);

            add(q[i].y,q[i].x,q[i].w);

        }

    }

}

void dfs(int u,int w)

{

    for(int v=head[u];v!=-1;v=ma[v].next)

    {

        int i=ma[v].to;

        if(vis[i])

            continue;

        dis[i]=max(w,ma[v].w);

        vis[i]=true;

        dfs(i,dis[i]);

    }

}

int main()

{

    int cas=1,T;

    int a,b,c;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d",&n,&m);

        num=0;

        while(m--)

        {

            scanf("%d%d%d",&a,&b,&c);

            q[num].x=a;

            q[num].y=b;

            q[num++].w=c;

        }

        scanf("%d",&t);

        init();

        memset(vis,false,sizeof(vis));

        memset(dis,-1,sizeof(dis));

        vis[t]=true;

        dfs(t,0);

        printf("Case %d:\n",cas++);

        for(int i=0;i<n;i++)

        {

            if(i==t)

                puts("0");

            else if(dis[i]==-1)

                puts("Impossible");

            else

                printf("%d\n",dis[i]);

        }

    }

    return 0;

}

最短路转化的代码：

#include<stdio.h>

#include<queue>

#include<string.h>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long LL;

const int INF=0x3f3f3f3f;

const LL mod=1e9+7;

const int N=5e2+10;

//struct asd{

//    int to;

//    int w;

//    int next;

//};

//asd q[N*N];

//int tol,head[N*N];

int ma[N][N];

int dis[N];

bool vis[N];

int n,m,t;

void spfa()

{

    queue<int>q;

    for(int i=0;i<n;i++)

    {

        vis[i]=false;

        dis[i]=INF;

    }

    vis[t]=1;

    dis[t]=0;

    q.push(t);

    while(!q.empty())

    {

        int u=q.front();

        q.pop();

        vis[u]=0;

        for(int i=0;i<n;i++)

        {

            if(ma[u][i]==-1) continue;

            if(dis[i]>max(dis[u],ma[u][i]))

            {

                dis[i]=max(dis[u],ma[u][i]);

                if(!vis[i])

                {

                    vis[i]=1;

                    q.push(i);

                }

            }

        }

    }

}

int main()

{

    int cas=1,T;

    int a,b,c;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d",&n,&m);

        memset(ma,-1,sizeof(ma));

        while(m--)

        {

            scanf("%d%d%d",&a,&b,&c);

            if(ma[a][b]==-1)

                ma[a][b]=ma[b][a]=c;

            else

                ma[a][b]=ma[b][a]=min(c,ma[a][b]);

        }

        scanf("%d",&t);

        spfa();

        printf("Case %d:\n",cas++);

        for(int i=0;i<n;i++)

        {

            if(dis[i]==INF)

                puts("Impossible");

            else

                printf("%d\n",dis[i]);

        }

    }

    return 0;

}

先

巴特西

Lightoj1002 【搜索】

最新文章

热门文章