分析：
一看到K的范围不大，就想到了枚举
两遍dijkstra得到起点到各点的单源最短路
以及终点到各点的单源最短路
枚举每一条商业线
dis=w(i,j)+dis1(i)+dis2(j)
注意
边都是双向的，所以在计算时间的时候也要双向考虑
dist=dis1[u]+v+dis2[w]; //双向边，所以要双向考虑
if (dist<ans)
{
ans=dist;
xx=u;
yy=w;
}
dist=dis1[w]+v+dis2[u];
if (dist<ans)
{
ans=dist;
xx=w;
yy=u;
}tip
题目说N<=500
结果500+的数组一直RE
最后直接开到了100000
出题人是干什么的，真搞不懂外国人是怎么想的
读入不要写×了不然会T的
在dijkstra的板子里，记录的是转移边
我为了省事，记录了转移点，结果就玄学的WA了
看来前辈用血的教训换来的经验是不容置疑的
真是被ACM的形式搞哭了
每次都有多组数据和方案输出，还不能有多余空格和空行
真的是心力憔悴
这些要求纯属是练码力
//这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
const int INF=0x33333333;
const int N=100000;
int n,S,T,m,k;
int dis1[N],dis2[N],p1[N],p2[N];
struct heapnode{ //dijkstra用到的优先队列的结点
int d,u; //d 距离，u 结点编号
bool operator <(const heapnode &a) const
{
return d>a.d;
}
//在优先队列中，是从大到小排序的，所以我们反向定义一下<号
};
struct node{
int x,y,v; //起点 终点 边权
};
//定义边的结构体
struct Dijkstra{
int n,m; //点和边的数目
vector<node> e; //存储边
vector<int> G[N]; //存储每个点所连的边的编号
bool p[N]; //已用标记
int dis[N]; //最短距离
int pre[N]; //每个点的转移边
void init(int n)
{
this->n=n;
e.clear();
for (int i=1;i<=n;i++) G[i].clear();
}
void add(int u,int w,int z) //加边
{
e.push_back((node){u,w,z}); //直接把边作为结构体塞进去
m=e.size();
G[u].push_back(m-1); //size是m，e中边是从0开始编号的
}
void dij(int s)
{
memset(dis,0x33,sizeof(dis));
memset(pre,0,sizeof(pre));
memset(p,1,sizeof(p));
dis[s]=0;
priority_queue<heapnode> Q;
Q.push((heapnode){0,s}); //距离和点的编号作为一个结构体直接塞进优先队列
while (!Q.empty())
{
heapnode now=Q.top(); Q.pop();
int u=now.u;
if (!p[u]) continue; //打过标记的不能作为转移点
p[u]=0; //千万不要忘了打标记
for (int i=0;i<G[u].size();i++) //循环和u相连的所有边
{
node way=e[G[u][i]];
if (dis[way.y]>dis[u]+way.v)
{
dis[way.y]=dis[u]+way.v;
pre[way.y]=G[u][i];
Q.push((heapnode){dis[way.y],way.y});
}
}
}
}
};
Dijkstra A;
void printA(int now)
{
if (now==S)
{
printf("%d",now);
return;
}
int t=p1[now];
node way=A.e[t];
printA(way.x);
printf(" %d",now);
}
void printB(int now)
{
if (now==T)
{
printf(" %d",now);
return;
}
printf(" %d",now);
int t=p2[now];
node way=A.e[t];
printB(way.x);
}
int main()
{
int cnt=0;
while (scanf("%d%d%d",&n,&S,&T)!=EOF)
{
if (cnt++) printf("
");
A.init(n);
scanf("%d",&m);
for (int i=1;i<=m;i++)
{
int u,w,v;
scanf("%d%d%d",&u,&w,&v);
A.add(u,w,v); A.add(w,u,v);
}
A.dij(S);
for (int i=1;i<=n;i++)
dis1[i]=A.dis[i],p1[i]=A.pre[i];
A.dij(T);
for (int i=1;i<=n;i++)
dis2[i]=A.dis[i],p2[i]=A.pre[i];
int ans=dis1[T]; //直接到达
int dist,xx=-1,yy=-1;
scanf("%d",&k);
for (int i=1;i<=k;i++)
{
int u,w,v;
scanf("%d%d%d",&u,&w,&v);
dist=dis1[u]+v+dis2[w]; //双向边，所以要双向考虑
if (dist<ans)
{
ans=dist;
xx=u; yy=w;
}
dist=dis1[w]+v+dis2[u];
if (dist<ans)
{
ans=dist;
xx=w; yy=u;
}
}
if (xx==-1)
{
printA(T);
printf("
");
printf("Ticket Not Used
");
}
else
{
printA(xx);
printB(yy);
printf("
");
printf("%d
",xx);
}
printf("%d
",ans);
}
return 0;
}