NC25235. 免费机票
描述
某华大学小飞中奖了！！！奖品是一张免费飞机票，唯一遗憾的是，这张飞机票有限定区间，需要从k个区间中选择其一。小飞打算高高兴兴的出去玩啦，但是，从s地出发，去往e地，可能没有直达的飞机票，可能需要转机（所有飞机线路都是无向的），小飞毕竟是个学生党，出去玩首先得考虑省钱，所以，小飞遇到麻烦了，请帮小飞计算最便宜的一条路线，小飞会很感激你的。
输入描述
第一行为三个整数n，s，e，n表示n个不同城市的飞机场，s为出发点，e为目的地。（1<=n<=1000, 1<=s,e<=n）
第二行为一个整数m，表示m条普通飞机线路，接下来的m行描述每条线路，每行包含三个整数a、b、c，a、b代表普通飞机线路两端，c表示价格。(1<=m<=1000, 1<=a,b<=n, 1<=c<=1000)
接下来的一行为一个整数k，表示k个免费机票的航线区间， 然后k行来描述每条免费航线，每行两个整数a’、b’， 分别代表免费航线两端。(1<=k<=1000, 1<=a’,b’<=n)
输出描述
每个测试数据有两行输出，第一行为是否使用免费飞机票，是则输出“Yes”，否则输出“No”。第二行输出总共花费。
示例1
输入:
4 1 4 3 1 2 1 1 3 2 2 4 3 1 3 4
输出:
Yes 2
示例2
输入:
7 1 7 5 1 4 1 1 5 2 1 7 10 4 7 8 5 7 5 2 2 4 6 7
输出:
No 7
C++11(clang++ 3.9) 解法, 执行用时: 902ms, 内存消耗: 4444K, 提交时间: 2019-04-21 22:15:02
#include<bits/stdc++.h>
using namespace std;
int n,s,e,m,a,b,k,c,i,j,mymap[1001][1001],ans,u,v;
int main()
{
int t,flag = 0;
cin>>n>>s>>e;
cin>>m;
memset(mymap,0x3f,sizeof(mymap));
for(i = 0;i<=n;i++)
{
mymap[i][i] = 0;
}
for(i = 0;i<m;i++)
{
cin>>a>>b>>c;
mymap[a][b] = c;
mymap[b][a] = c;
}
for(k = 1;k<=n;k++)
for(i = 1;i<=n;i++)
for(j = 1;j<=n;j++)
if(mymap[i][j]>mymap[i][k]+mymap[k][j])
mymap[i][j]=mymap[i][k]+mymap[k][j];
ans = mymap[s][e];
cin>>k;
while(k--)
{
cin>>u>>v;
if(ans>mymap[s][u]+mymap[v][e]||ans>mymap[s][v]+mymap[u][e])
{
flag = 1;
ans = min(mymap[s][u]+mymap[v][e],mymap[s][v]+mymap[u][e]);
}
}
if(flag)
{
cout<<"Yes"<<endl;
cout<<ans;
}
else
{
cout<<"No"<<endl;
cout<<ans;
}
return 0;
}