HDU1224 Free DIY Tour（spfa+記錄路徑）

題目位址：http://acm.hdu.edu.cn/showproblem.php?pid=1

記錄路徑不會，于是又拜訪了一下各個牛人的部落格，真是慚愧。。無奈牛人都是用DP做的。。。sad。。。好不容易找到一個用spfa做的，寫的亂七八糟。。不不。。是寫的很進階，連加邊都寫得那麼進階，實在看不懂，。不過有了思路。于是現學的spfa。。記錄路徑其實就是在松弛的過程中記錄路徑。然後在最後最短路求完後再回溯，把路徑求出來。然後輸出即可。這題調試了好長時間。。。終于調試成功了。。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include<algorithm>

using namespace std;
int n, m, vis[200], d[200], head[200], maxint=0,p[200], per[200],lu[200], cnt;
struct node
{
    int v, w, next;
}edge[10000];
void add(int u, int v, int w)
{
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
void spfa(int s)
{
    int i;
    queue<int>q;
    for(i=0;i<=n;i++)
        d[i]=maxint;
    d[s]=0;
    vis[s]=1;
    q.push(s);
    while(!q.empty())
    {
        int f=q.front();
        q.pop();
        vis[f]=0;
        for(i=head[f];i!=-1;i=edge[i].next)
        {
            if(d[edge[i].v]<edge[i].w+d[f])
            {
                d[edge[i].v]=edge[i].w+d[f];
                //printf("%d %d\n",edge[i].v,d[edge[i].v]);
                per[edge[i].v]=f;
                //printf("%d %d\n",edge[i].v,f);
                if(!vis[edge[i].v])
                {
                    vis[edge[i].v]=1;
                    q.push(edge[i].v);
                }
            }
        }
    }
}
int main()
{
    int t, i, a, b, num=0, j;
    scanf("%d",&t);
    while(t--)
    {
        num++;
        memset(head,-1,sizeof(head));
        memset(vis,0,sizeof(vis));
        memset(edge,0,sizeof(edge));
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&p[i]);
        }
        p[++n]=p[1];
        scanf("%d",&m);
        while(m--)
        {
            scanf("%d%d",&a,&b);
            if(a>b)
            {
                int t=a;
                a=b;
                b=t;
            }
            add(a,b,p[b]);
        }
        cnt=0;
        spfa(1);
        printf("CASE %d#\n",num);
        printf("points : %d\n",d[n]);
        printf("circuit : 1");
        cnt=0;
        /*for(i=1;i<=n;i++)
            printf("%d ",per[i]);
        printf("\n");*/
        for(j=per[n];j!=1;j=per[j])
        {
            lu[cnt++]=j;
        }
        for(j=cnt-1;j>=0;j--)
        {
            printf("->%d",lu[j]);
        }
        printf("->1\n");
        if(t!=0)
            printf("\n");
    }
    return 0;
}