题目思路
主要还是迪杰斯特拉算法,附加堆优化
注意图的构建方法是针对某条线路有两个站点,那么这两个站点就会有一条边连接
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=10010,M=1e6+10;
int h[N],s[M],e[M],he[M],len[M],line[M],id=0;
int dis[N],cnt[N];
bool vis[N];
int stop[N];
void add(int a,int b,int c,int d)
{
s[id]=a; //起点
e[id]=b; //终点
line[id]=c; //几号线
len[id]=d; //边长
he[id]=h[a];
h[a]=id++;
}
void dji(int a,int b)
{
memset(dis,0x3f3f3f3f,sizeof(dis));
memset(vis,false,sizeof(vis));
memset(cnt,0x3f3f3f3f,sizeof(cnt));
priority_queue<PII,vector<PII>,greater<PII>> que;
que.push({0,a});
dis[a]=0;
cnt[a]=0;
vector<int>path(N);
while(!que.empty())
{
auto p=que.top();
que.pop();
int to=p.second,d=p.first;
if(to==b) break;
if(vis[to]) continue;
vis[to]=true;
for(int i=h[to];i!=-1;i=he[i])
{
int tn=e[i];
if(dis[tn]>d+len[i])
{
dis[tn]=d+len[i];
cnt[tn]=cnt[to]+1;
que.push({dis[tn],tn});
//记录路径
path[tn]=i;
}
else if(dis[tn]==d+len[i])
{
if(cnt[tn]>cnt[to]+1)
{
cnt[tn]=cnt[to]+1;
que.push({dis[tn],tn});
//记录路径
path[tn]=i;
}
}
}
}
cout<<dis[b]<<'\n';
stack<int>pn; //存边的id
int p1=0,p2=0;
int i=path[b];
for(;s[i]!=a;i=path[s[i]]) //s[i]为边i的起点,e[i]为边i的终点
{
p1=line[i];
if(p1!=p2)
{
pn.push(i);
}
p2=p1;
}
pn.push(i);
while(!pn.empty())
{
i=pn.top();
pn.pop();
cout<<"Take Line#"<<line[i]<<" from "<<setw(4)<<setfill('0')<<s[i]<<" to "<<setw(4)<<e[i]<<".\n"; //注意四位数输出
//setw()只作用一次<< ; setfill()可以持续
}
}
int main()
{
memset(h,-1,sizeof(h));
int n,q;
cin>>n;
for(int i=1;i<=n;++i)
{
int l;
cin>>l;
for(int t=0;t<l;++t)
cin>>stop[t];
for(int t=0;t<l;++t) //构建的图是全局的,只要某条线两个站点能到,那么就存在边
{
for(int j=t+1;j<l;++j)
{
int len=j-t;
if(stop[0]==stop[l-1]) //环路
{
len=min(len,l-1-len);
}
add(stop[t],stop[j],i,len);
add(stop[j],stop[t],i,len);
}
}
}
cin>>q;
while(q--)
{
int a,b;
cin>>a>>b;
dji(a,b);
}
}