程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 27/7/2012 ICPC培訓

27/7/2012 ICPC培訓

編輯：C++入門知識

眨眼培訓就過了大半喽。我還是很喜歡的。。。
上午做了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()
{
    while(scanf("%d",&numEdge)==1,numEdge!=-1)
    {
        if(numEdge==0)
        {
            getchar();
            scanf("%s%s",&start,&end);

            if(strcmp(start,end)==0) printf("0\n");
            else printf("-1\n");

            continue;
        }

        input();

        buildMap();

        SPFA();
    }

    system("pause");
    return 0;
}