poj2263 zoj1952 Heavy Cargo(floyd||spfa)

这道题数据范围小，方法比较多。我用floyd和spfa分别写了一下，spfa明显有时间优势。

一个小技巧在于：把城市名称对应到数字序号，处理是用数字。

方法一：spfa

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<string>

#include<cmath>

#include<map>

#include<set>

#include<vector>

#include<algorithm>

#include<stack>

#include<queue>

#include<cctype>

#include<sstream>

using namespace std;

#define pii pair<int,int>

#define LL long long int

const int eps=1e-;

const int INF=;

const int maxn=+;

int n,r,cas=,ton,num,used[maxn],d[maxn],m[maxn][maxn];

char city[maxn][];

char s[],e[];

vector<int>v[maxn];

int index(char *ss)

{

    int i;

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

    {

        if(strcmp(ss,city[i])==)

        {

            return i;

        }

    }

    strcpy(city[num++],ss);

    return i;

}

void ini()

{

    num=;

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

    {

        strcpy(city[i],"\0");

        v[i].clear();

        used[i]=;

        d[i]=INF;

    }

}

int spfa(int s,int e)

{

    queue<int>q;

    q.push(s);

    used[s]=;

    while(!q.empty())

    {

        int t=q.front();

        used[t]=;

        q.pop();

        int siz=v[t].size();

        for(int i=;i<siz;i++)

        {

            int k=v[t][i];

            /*if(used[k]==0) {q.push(k);used[k]=1;}

            if(d[k]<INF) d[k]=max(d[k],min(d[t],m[t][k]));

            else d[k]=min(d[t],m[t][k]);*/

            /*上面注释掉的这种写法不对，一旦有环就会陷入死循环（即使这题不会有

            负边）。还是对spfa理解的不够。需要更新的点才要考虑入队的问题，不需要

            更新的点肯定不入队，最后所有点都不用再更新了队列为空退出循环。而不是

            遇到一个点就入队。*/

            if(d[k]==INF)

            {

                d[k]=min(d[t],m[t][k]);

                q.push(k);used[k]=;

            }

            else if(min(d[t],m[t][k])>d[k])

            {

                d[k]=min(d[t],m[t][k]);

                if(used[k]==) {q.push(k);used[k]=;}

            }

        }

    }

    return d[e];

}

int main()

{

    //freopen("in8.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    while(scanf("%d%d",&n,&r)==)

    {

        if(n==&&r==) break;

        printf("Scenario #%d\n",++cas);

        ini();

        for(int i=;i<r;i++)

        {

            scanf("%s%s%d",s,e,&ton);

            int t1=index(s);

            int t2=index(e);

            v[t1].push_back(t2);

            v[t2].push_back(t1);

            m[t1][t2]=m[t2][t1]=ton;

        }

        scanf("%s%s",s,e);

        int t1=index(s);

        int t2=index(e);

        printf("%d tons\n",spfa(t1,t2));

        printf("\n");

    }

    //fclose(stdin);

    //fclose(stdout);

    return ;

}

spfa

方法二：floyd

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<string>

#include<cmath>

#include<map>

#include<set>

#include<vector>

#include<algorithm>

#include<stack>

#include<queue>

#include<cctype>

#include<sstream>

using namespace std;

#define pii pair<int,int>

#define LL long long int

const int eps=1e-;

const int INF=;

const int maxn=+;

int n,r,m[maxn][maxn],cas=,ton,num;

char city[maxn][];

char s[],e[];

int index(char *ss)

{

    int i;

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

    {

        if(strcmp(ss,city[i])==)

        {

            return i;

        }

    }

    strcpy(city[num++],ss);

    return i;

}

void floyd()

{

    for(int k=;k<n;k++)

    {

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

        {

            for(int j=;j<n;j++)

            {

                m[i][j]=max(m[i][j],min(m[i][k],m[k][j]));

            }

        }

    }

}

void ini()

{

    num=;

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

    {

        strcpy(city[i],"\0");

        for(int j=;j<n;j++)

        {

            if(i==j) m[i][j]=INF;

            else m[i][j]=;

        }

    }

}

int main()

{

    //freopen("in8.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    while(scanf("%d%d",&n,&r)==)

    {

        if(n==&&r==) break;

        printf("Scenario #%d\n",++cas);

        ini();

        for(int i=;i<r;i++)

        {

            scanf("%s%s%d",s,e,&ton);

            int t1=index(s);

            int t2=index(e);

            m[t1][t2]=m[t2][t1]=ton;

        }

        floyd();

        scanf("%s%s",s,e);

        int t1=index(s);

        int t2=index(e);

        printf("%d tons\n",m[t1][t2]);

        printf("\n");

    }

    //fclose(stdin);

    //fclose(stdout);

    return ;

}

floyd