27/7/2012 ICPC培训

眨眼培训就过了大半喽。我还是很喜欢的。。。
上午做了HDU2112
还是求最短路径的，不同的是这题没有直接给地点标号，需要我们来处理。
这题要注意一下集中情况：
1、start、end地点在下面的路径中不一点会出现，所以在标号时需要对这两个点也处理。
2、无向图的处理可能会增加时间复杂度，但不会改变最短路径的长度，因为除非是负权边，
否则a->b被处理过，b->a一点不会被处理了。
3、这题的建图。利用temp[][]表将地点不重复地存储起来，建立地点和数字标号间的唯一对应
关系。然后在查找建图。
4、SPFA算法，不仅仅可以求出最短路径，还可以判断两点是否连通。（有向图、无向图均可）
代码：
[cpp]
#include<iostream>
#include<vector>
#include<queue>
using namespace std;

const int maxRoad=10001; //路径数
const int maxSize=151;    //地点数
const int maxLen=31;      //地点的最大长度
const int INF=0x7fffffff;

struct node   //边
{
    char start[maxLen];
    char end[maxLen];
    int from;
    int to;
    int cost;
}edge[maxRoad];

int minPath[maxSize];   //最短路
bool inQ[maxSize];       //是否在队列中
int numEdge,numAdress,from,to; //路径数、点数、起点、终点
char start[maxLen],end[maxLen];
char temp[maxSize][maxLen];    //不重复存放地存放每个点
vector<node> myV[maxSize];     //连接表

int findIndex(char c[])   //找地点的标示
{
    for(int i=0;i<numAdress;i++)
    {
        if(strcmp(c,temp[i])==0)
        {
            return i;
        }
    }

    return -1;
}

void input()
{
    numAdress=0;
    getchar();
    scanf("%s%s",&start,&end);

    //如果不在temp[][]表中就放进去
    if(findIndex(start)==-1) strcpy(temp[numAdress++],start);
    if(findIndex(end)==-1) strcpy(temp[numAdress++],end);

    for(int i=0;i<numEdge;i++)
    {
        getchar();
        scanf("%s%s%d",&edge[i].start,&edge[i].end,&edge[i].cost);

        if(findIndex(edge[i].start)==-1) strcpy(temp[numAdress++],edge[i].start);
        if(findIndex(edge[i].end)==-1) strcpy(temp[numAdress++],edge[i].end);
    }
}

void buildMap()
{
    for(int j=0;j<maxSize;j++)
    {
        myV[j].clear();
    }

    from=findIndex(start);
    to=findIndex(end);

    for(int i=0;i<numEdge;i++)
    {
        //建立无向图
        edge[i].from=findIndex(edge[i].start);
        edge[i].to=findIndex(edge[i].end);
        myV[edge[i].from].push_back(edge[i]);

        edge[i].to=findIndex(edge[i].start);
        edge[i].from=findIndex(edge[i].end);
        myV[edge[i].from].push_back(edge[i]);
    }
}

void SPFA()
{
    for(int i=0;i<maxSize;i++) minPath[i]=INF;
    minPath[from]=0;
    memset(inQ,false,sizeof(inQ));
    inQ[from]=true;

    queue<int> myQ;
    myQ.push(from);

    while(!myQ.empty())
    {
        int from,to,cost;
        from=myQ.front();
        myQ.pop();

        for(int j=0;j<myV[from].size();j++)
        {
            to=myV[from][j].to;
            cost=myV[from][j].cost+minPath[from];

            if(cost<minPath[to])
            {
                minPath[to]=cost;

                if(!inQ[to])
                {
                    inQ[to]=true;
                    myQ.push(to);
                }
            }
        }

        inQ[from]=false;
    }

    if(minPath[to]!=INF) printf("%d\n",minPath[to]);
    else printf("-1\n");
}

int main()
{
    whil

补充：软件开发 , C++ ,