最短路问题。
从起点和终点开始各跑一次dijkstra，可以得到起点、终点到任意点的距离。枚举使用的商业线路，找最优解。
破题卡输出，记录前驱和输出什么的仿佛比算法本身还麻烦。
/*by SilverN*/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int mxn=;
int read(){
int x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int n,m,k,S,E;
struct exp{
int x,y,w;
}ex[mxn];
struct edge{
int v,nxt,dis;
}e[mxn<<];
int hd[mxn],mct=;
void add_edge(int u,int v,int d){
e[++mct].v=v;e[mct].nxt=hd[u];e[mct].dis=d;hd[u]=mct;
return;
}
struct node{
int v,d;
bool operator < (const node r) const {return d>r.d;}
};
priority_queue<node>tp;
int pre[mxn],nxt[mxn];
int dis[mxn];
int mdis[mxn];
void Dij1(int st){
while(!tp.empty())tp.pop();
memset(dis,0x3f,sizeof dis);
tp.push((node){st,});
dis[st]=;
while(!tp.empty()){
node tmp=tp.top();tp.pop();
if(tmp.d>dis[tmp.v])continue;
int u=tmp.v;
for(int i=hd[u];i;i=e[i].nxt){
int v=e[i].v;
if(dis[v]>dis[u]+e[i].dis){
dis[v]=dis[u]+e[i].dis;
pre[v]=u;
tp.push((node){v,dis[v]});
}
}
}
return;
}
void Dij2(int st){
while(!tp.empty())tp.pop();
memset(dis,0x3f,sizeof dis);
tp.push((node){st,});
dis[st]=;
while(!tp.empty()){
node tmp=tp.top();tp.pop();
if(tmp.d>dis[tmp.v])continue;
int u=tmp.v;
for(int i=hd[u];i;i=e[i].nxt){
int v=e[i].v;
if(dis[v]>dis[u]+e[i].dis){
dis[v]=dis[u]+e[i].dis;
nxt[v]=u;
tp.push((node){v,dis[v]});
}
}
}
return;
}
int st[mxn],top=;
void init(){
memset(hd,,sizeof hd);
memset(pre,,sizeof pre);
memset(nxt,,sizeof nxt);
mct=;top=;
} int main(){
int i,j;
bool flag=;
while(scanf("%d%d%d%d",&n,&S,&E,&m)!=EOF){
if(flag){
printf("\n");
}
flag=;
init();
int u,v,w;
for(i=;i<=m;i++){
u=read();v=read();w=read();
add_edge(u,v,w);
add_edge(v,u,w);
}
k=read();
for(i=;i<=k;i++){
ex[i].x=read();ex[i].y=read();
ex[i].w=read();
}
Dij1(S);
memcpy(mdis,dis,sizeof dis);
Dij2(E);
int pos1=,pos2=,ans=1e9;
for(i=;i<=n;i++){
if(ans>mdis[i]+dis[i]){
ans=mdis[i]+dis[i];
pos1=i;
}
}
for(i=;i<=k;i++){
int tmp=mdis[ex[i].x]+dis[ex[i].y]+ex[i].w;
if(ans>tmp){
ans=tmp;pos1=ex[i].x;pos2=ex[i].y;
}
tmp=mdis[ex[i].y]+dis[ex[i].x]+ex[i].w;
if(ans>tmp){
ans=tmp;pos1=ex[i].y;pos2=ex[i].x;
}
}
if(pos1 && !pos2){
// printf("Test1\n");
int tmp=pos1;
while(pre[pos1]){
pos1=pre[pos1];
st[++top]=pos1;
}
while(top) printf("%d ",st[top--]);
pos1=tmp;
do{
printf("%d",pos1);
if(nxt[pos1])printf(" ");
pos1=nxt[pos1];
}while(pos1);
printf("\nTicket Not Used\n");
}
else{
if(pos1 && pos2){
int tmp=pos1;
while(pre[pos1]){
pos1=pre[pos1];
st[++top]=pos1;
}
while(top) printf("%d ",st[top--]);
pos1=tmp;
printf("%d ",pos1);
// pos2=nxt[pos2];
while(pos2){
printf("%d",pos2);
if(nxt[pos2])printf(" ");
pos2=nxt[pos2];
}
printf("\n%d\n",pos1);
}
}
printf("%d\n",ans);
}
return ;
}