这题要记录某点的最短路是从哪个边过来的，所有不能用vector的方式建图（虽然我很喜欢这么做）。
这题有下面几点注意：
1.要用数组模拟链表的方式建图，因为这样会给每条边编上号，这是vector建图做不到的。
2.要注意对环路这种情况进行特判。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=10000+5,M=1e6+5;

int h[N],e[M],ne[M],line[M],w[M],idx;
int dist[N],cnt[N],path[N],pre[N];
bool st[N];
void add(int a,int b,int v,int id)
{
    line[idx]=id,e[idx]=b,w[idx]=v,ne[idx]=h[a],h[a]=idx++;
}

void dij(int s,int E)
{
    memset(dist,0x3f,sizeof dist);
    dist[s]=0;
    memset(cnt,0x3f,sizeof cnt);
    cnt[s]=0;
    memset(path,-1,sizeof path);
    memset(pre,-1,sizeof pre);
    memset(st,0,sizeof st);
    priority_queue<PII,vector<PII>,greater<PII>> q;
    q.push({0,s});
    while(q.size())
    {
        auto t=q.top();q.pop();
        int x=t.second;
        if(st[x]) continue;
        st[x]=true;
        for(int i=h[x];~i;i=ne[i])
        {
            int j=e[i];

            if(dist[j]>dist[x]+w[i])
            {
                dist[j]=dist[x]+w[i];
                path[j]=x;
                cnt[j]=cnt[x]+1;
                pre[j]=line[i];
                q.push({dist[j],j});
            }else if(dist[j]==dist[x]+w[i]&&cnt[j]>cnt[x]+1)
            {
                cnt[j]=cnt[x]+1;
                path[j]=x;
                pre[j]=line[i];
            }
        }
    }
    cout<<dist[E]<<endl;
    vector<int> ans;
    int cur=E;
    while(cur!=-1)
    {
        ans.push_back(cur);
        cur=path[cur];
    }
    reverse(ans.begin(),ans.end());
    for(int i=1;i<ans.size();i++)
    {
        int x=ans[i-1],y=ans[i];
        printf("Take Line#%d from %04d to %04d.\n",pre[y],x,y);
    }

}

int main()
{
    int n,m;
    memset(h,-1,sizeof h);
    //freopen("in.txt","r",stdin);
    cin>>n;
    int tmp[110],x,num=0;
    for(int u=1;u<=n;u++)
    {
        cin>>m;
        num=0;
        while(m--)
        {
            cin>>x;
            tmp[num++]=x;
        }
        for(int j=0;j<num;j++)
            for(int k=j+1;k<num;k++)
            {
                int x=tmp[j],y=tmp[k];
                int d=k-j;
                if(tmp[0]==tmp[num-1]) d=min(d,num-1-d);
                add(x,y,d,u),add(y,x,d,u);
            }
    }
    cin>>n;
    while(n--)
    {
        int x,y;
        cin>>x>>y;
        dij(x,y);
    }
}