题意：给好多个城市的机票价格，旅行过程中可以把某张机票价格减半。求城市A到城市B的最小费用。
思路：求出A到每个城市的价格和B到每个城市的价格，遍历每条边求出最小价格。写完spfa就各种wa，找了一下午。开始我以为是无向图，就建了一个图。算B到每个城市价格的时候就错了，应该建反向图的。
代码：
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <deque>
#include <set>
#include <string>
using namespace std;
#define For(i,a) for(i=0;i<a;i++)
#define Foru(i,a,b) for(i=a;i<=b;i++)
#define Ford(i,a,b) for(i=a;i>=b;i--)
#define clr(ar,vel) memset(ar,vel,sizeof(ar))
#define PB push_back
#define maxint 0x7fffffff
const long long maxll =1LL<<60;
typedef long long ll;
const int maxn = 100010;
struct edge{int to, dis;};
vector<edge> G[maxn], GB[maxn];
map<string, int> ma;
bool vis[maxn];
ll s_dis[maxn], t_dis[maxn];
int n, m, cnt;
int getNum(string s){
if( !ma.count(s)) return ma[s] = cnt++;
else return ma[s];
}
void spfa(int s, ll *dis, vector<edge> *G){
memset(vis, 0, sizeof(vis));
fill(dis, dis+n, maxll);
deque<int> q;
q.push_back(s);
vis[s] = 1;
dis[s] = 0;
while(q.size()){
int fn = q.front(); q.pop_front();
vis[fn] = 0;
for(int i = 0; i < G[fn].size(); i ++){
int to = G[fn][i].to;
int vel = G[fn][i].dis;
if( dis[to] > dis[fn] + vel) {
dis[to] = dis[fn] + vel;
if( !vis[to]) {
if( q.size() && dis[to] < dis[q.front()]) q.push_front(to);
else q.push_back(to);
vis[to] = 1;
}
}
}
}
}
int main(){
ios::sync_with_stdio(false);
string f, t;
int dis, from, to;
while(cin >> n >> m){
// cout << maxint << ' ' << maxll << endl;
for(int i = 0; i < n; i ++) {
G[i].clear();
GB[i].clear();
}
ma.clear();
cnt = 0;
while(m--){
cin >> f >> t >> dis;
from = getNum(f); to = getNum(t);
G[from].push_back((edge){to, dis});
GB[to].push_back((edge){from, dis});
}
cin >> f >> t;
from = getNum(f); to = getNum(t);
spfa(from, s_dis, G);
spfa(to, t_dis, GB);
ll ans = maxll;
for(int i = 0; i < n; i ++){
for(int j = 0; j < G[i].size(); j ++){
int t = G[i][j].to;
dis = G[i][j].dis;
if( s_dis[i] < maxll && t_dis[t] < maxll ) ans = min(ans, s_dis[i] + t_dis[t] + dis/2);
}
}
if( ans >= maxll ) ans = -1;
cout << ans << endl;
}
return 0;
}