题意：
给一幅图，要从s点要到e点，图中有两种无向边分别在两个集合中，第一个集合是可以无限次使用的，第二个集合中的边只能挑1条。问如何使距离最短？输出路径，用了第二个集合中的哪条边，最短距离。
思路：
（1）简单易操作方法：既然第二个集合的边只能有1条，就穷举下这些边，可能的边集进行求最短路，同时记录3个答案。复杂度是O(m*k)。
（2）时间复杂度低：不妨先求从s到每个其他点的距离d1[i]，再求e到其他每个点的距离d2[i]，接下来穷举第二个集合中的每条边u-v，那么最短距离为d1[u]+dis[u][v]+d2[v]，注意边是无向的。麻烦在记录路径而已，还是挺容易操作的。复杂度是O(2m+k)。
下面是第一种方法的代码：
#include <bits/stdc++.h>
#define LL long long
#define pii pair<int,int>
#define INF 0x7f7f7f7f
using namespace std;
const int N=;
int n, m, k;
vector<int> vect[N];
int edge_cnt;
struct node
{
int from, to, dis, tag;
node(){};
node(int from,int to,int dis,int tag):from(from),to(to),dis(dis),tag(tag){};
}edge[N*]; void add_node(int from,int to,int dis,int tag)
{
edge[edge_cnt]=node(from,to,dis,tag);
vect[from].push_back(edge_cnt++);
} int tag[N], dist[N], vis[N], path[N];
int dijkstra(int s,int e)
{
memset(dist,0x7f,sizeof(dist));
memset(tag,,sizeof(tag));
memset(vis,,sizeof(vis));
memset(path,,sizeof(path)); priority_queue<pii,vector<pii>,greater<pii> > que;
que.push(make_pair(, s));
dist[s]=; while(!que.empty())
{
int x=que.top().second;
que.pop();
if(vis[x]) continue;
vis[x]=;
for(int i=; i<vect[x].size(); i++)
{
node e=edge[vect[x][i]];
if( e.tag> && dist[e.to]>dist[x]+e.dis )
{
dist[e.to]=dist[x]+e.dis;
path[e.to]=x;
if(e.tag==)
{
tag[e.to]=true; //到这个点用了快线
}
que.push( make_pair(dist[e.to],e.to) );
}
}
}
return dist[e];
} void cal(int s ,int e)
{
vector<int> ans;
int quick=, big=dijkstra(s,e), d=e;//先跑了一遍不用快线的 while( d )
{
ans.push_back(d);
d=path[d];
} for(int i=m*; i<(m+k)*; i+= ) //穷举每条可以用的快线
{
edge[i].tag=;
edge[i+].tag=; int dis=dijkstra(s,e);
if( dis<big )
{
big=dis;
ans.clear();
int ed=e, tmp=;
while( ed )
{
if( tag[ed] ) tmp=path[ed]; //有可能没有用到
ans.push_back(ed);
ed=path[ed];
}
quick=tmp;//如果没有用到，也会及时更新为0
}
edge[i].tag=;
edge[i+].tag=;
} reverse(ans.begin(),ans.end());
printf("%d",ans[]); //千万注意输出格式
for(int i=; i<ans.size(); i++) printf(" %d",ans[i]);
printf("\n"); if(quick) printf("%d\n",quick);
else puts("Ticket Not Used");//别忘了 printf("%d\n",big);
} int main()
{
freopen("input.txt", "r", stdin);
int s=, e, a, b, c, ttt=;
while(~scanf("%d%d%d", &n, &s, &e))
{
if(ttt) printf("\n");ttt++;//格式啊！
edge_cnt=;
memset(edge,,sizeof(edge));
for(int i=; i<=n; i++) vect[i].clear();
scanf("%d",&m);
for(int i=; i<m; i++)
{
scanf("%d%d%d",&a,&b,&c);
add_node(a,b,c,);
add_node(b,a,c,);
}
scanf("%d",&k);
for(int i=; i<k; i++)
{
scanf("%d%d%d",&a,&b,&c);
add_node(a,b,c,);
add_node(b,a,c,);
}
cal(s,e);
}
return ;
}
AC代码