最短路。
把题目抽象一下：已知一张图，边上的权值表示长度。现在又有一些边，只能从其中选一条加入原图，使起点->终点的距离最小。
当加上一条边a->b，如果这条边更新了最短路，那么起点st->终点ed的最小距离=st->a + a->b +b->ed 三个值的最短距离之和。于是正反求两次单元最短路。再将k条边遍历一遍就好了。
最近在改代码风格，写起来很别扭。。uva又挂了，最让我不理解的是http://www.cnblogs.com/arbitrary/archive/2013/02/06/2908099.html这个家伙的代码竟然能ac，问题是我稍微改一下就submission error，难道代码还能防盗= =
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#define clr(a,x) memset(a,x,sizeof(a));
#define ref(i,a,b) for(int i=a;i<=b;i++)
using namespace std; const int MAXN=;
const int INF =; struct Edge{
int u,v,c;
}; struct Node{
int d,u;
bool operator <(const Node x)const {
return d>x.d;
}
}; struct Dij{
int n,m;
vector<Edge>edge;
vector<int>G[MAXN];
bool vis[MAXN];
int d[MAXN];
int p[MAXN]; void init(int n)
{
this->n=n;
ref(i,,n-)G[i].clear();
edge.clear();
} void add(int u,int v,int c)
{
edge.push_back((Edge){u,v,c});
m=edge.size();
G[u].push_back(m-);
} void dij(int st)
{
priority_queue<Node>q;
ref(i,,n-)d[i]=(i==st)?:INF;
clr(vis,);
q.push((Node){,st});
while(!q.empty())
{
Node x=q.top();
q.pop();
int u=x.u;
if(vis[u])
continue;
vis[u]=true;
ref(i,,G[u].size()-){
Edge e=edge[G[u][i]];
if(d[e.v]>d[u]+e.c){
d[e.v]=d[u]+e.c;
p[e.v]=G[u][i];
q.push((Node){d[e.v],e.v});
}
}
}
}
}; Dij solver;
int d1[MAXN],d2[MAXN];
int p[MAXN]; int main()
{
int cnt=;
int n,m,k,st,ed;
while(~scanf("%d%d%d",&n,&st,&ed))
{
if(cnt++)
puts(""); st--;ed--;
solver.init(n); int u,v,c;
scanf("%d",&m);
ref(i,,m-){
scanf("%d%d%d",&u,&v,&c);
u--;v--;
solver.add(u,v,c);
solver.add(v,u,c);
} solver.dij(st);
ref(i,,n-)
d1[i]=solver.d[i]; solver.dij(ed);
ref(i,,n-){
d2[i]=solver.d[i];
p[i]=solver.p[i];
}
p[ed]=-; scanf("%d",&k);
int s=d1[ed],a,b;
a=b=-;
ref(i,,k-){
scanf("%d%d%d",&u,&v,&c);
u--;v--;
if(s>d1[u]+c+d2[v]){
s=d1[u]+c+d2[v];
a=u;b=v;
}
if(s>d1[v]+c+d2[u]){
s=d1[v]+c+d2[u];
a=v;b=u;
}
} int flog=;
if(a==-){ //不乘商务车
int x=st; while(x!=ed)
{
if(!flog){printf("%d",x+);flog=;}
else printf(" %d",x+);
x=solver.edge[p[x]].u; //p[]中保存的是 u->v 这条边的序号
}
printf(" %d",ed+);
printf("\nTicket Not Used\n%d\n",s);
}else{ //乘坐商务车
int x=st;
while(x!=a)
{
if(!flog){printf("%d",x+);flog=;}
else printf(" %d",x+);
x=solver.edge[p[x]].u;
}
if(x!=st)printf(" %d",x+);
else printf("%d",x+);
x=b;
while(x!=ed)
{
printf(" %d",x+);
x=solver.edge[p[x]].u;
}
printf(" %d\n",ed+);
printf("%d\n%d\n",a+,s);
}
}
return ;
} /*
4 1 4
4
1 2 2
1 3 3
2 4 4
3 4 5
1
1 4 7 2 1 2
1
1 2 2
1
1 2 1
*/