题意：裸的dijkstra 加上交通方式这一说 就是说如果在某个城市改变交通方式 那也要花钱
问你最少花费多少
思路：dis[4][maxn] 代表以某种方式到某一点时最小的花费
分情况更新即可
更新的核心代码：

		//最外层枚举到起点的所有路径的花费//再枚举所有终点//再枚举到终点所有路径的花费//如果两者路径相同 就不加那一点的花费 否则加上那一点的花费for(int k=0;k<=3;k++){if(dis[k][u]==inf) continue;for(int j=1;j<=n;j++){for(int l=0;l<=3;l++){if(g[l][u][j]==inf) continue;if(l==k){if(dis[l][j]>dis[k][u]+g[l][u][j]){dis[l][j]=dis[k][u]+g[l][u][j];}}else{if(dis[l][j]>dis[k][u]+g[l][u][j]+cost[u]){dis[l][j]=dis[k][u]+g[l][u][j]+cost[u];}}}}}

下面是AC代码 3000+ms 不建议用。。。如果用堆优化应该快一些！但是不知道咋用

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#define ll long long
#define inf 0x3f3f3f3f
#define sd(a) scanf("%d",&a)
#define sdd(a,b) scanf("%d%d",&a,&b)
#define cl(a,b) memset(a,b,sizeof(a))
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define sddd(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define dbg() printf("aaa\n")
using namespace std;
const int maxn=410;
int n,s,t;
int cost[maxn];
int g[4][maxn][maxn];
int dis[4][maxn];//表示用某种交通工具到某点所需要的最短时间
bool con[maxn];
map<string,int> mp;
void dijkstra(){cl(dis,inf);cl(con,0);//dis[0][s]=dis[1][s]=dis[2][s]=dis[3][s]=0;con[s]=1;rep(i,1,n){rep(j,0,3){dis[j][i]=g[j][s][i];}}for(int i=1;i<=n-1;i++){int u=-1,maxx=inf;for(int j=1;j<=n;j++){if(con[j]) continue;for(int k=0;k<=3;k++){if(maxx>dis[k][j]){maxx=dis[k][j];u=j;}}}con[u]=true;for(int k=0;k<=3;k++){if(dis[k][u]==inf) continue;for(int j=1;j<=n;j++){for(int l=0;l<=3;l++){if(g[l][u][j]==inf) continue;if(l==k){if(dis[l][j]>dis[k][u]+g[l][u][j]){dis[l][j]=dis[k][u]+g[l][u][j];}}else{if(dis[l][j]>dis[k][u]+g[l][u][j]+cost[u]){dis[l][j]=dis[k][u]+g[l][u][j]+cost[u];}}}}}}
}
int main() {mp["AIR"]=0;mp["SEA"]=1;mp["RAIL"]=2;mp["TRUCK"]=3;int T;sd(T);while(T--){cl(g,inf);sd(n);rep(i,1,n){string s;int tp;cin>>s>>tp;mp[s]=i;cost[i]=tp;g[0][i][i]=g[1][i][i]=g[2][i][i]=g[3][i][i]=0;}int m;sd(m);string u,v,op;rep(i,1,m){int c;cin>>u>>v>>op>>c;g[mp[op]][mp[u]][mp[v]]=c;g[mp[op]][mp[v]][mp[u]]=c;}cin>>u>>v;s=mp[u],t=mp[v];dijkstra();int min1=dis[0][t]<dis[1][t]?dis[0][t]:dis[1][t];int min2=dis[2][t]<dis[3][t]?dis[2][t]:dis[3][t];printf("%d\n",min1<min2?min1:min2);}getchar();getchar();return 0;
}