题目分析：
由于战争，一个商人想从城市1，回到自己的家城市2，其中城市1始终是由领导1，城市2始终由领导2，其中，商人回家的路中只能有一条路上连接由两个领导领导的城市，还有就是给出的路上双向的，也就是如果城市1能到城市2，那么城市2也同样能到城市1，这是关键。
由于这个题中从1类城市走到2类城市后就不能再回去，只能穿过一次，所以先存为双向路，后面再根据不同类型的城市，把双向路变为单向路
N个城市，城市编号为1,2,3，……N
M条路,路为双向路。 提供每条路的长度及端点城市编号,每两个城市之间直接连通的路最多一条。
这N个城市分为两个集合，部分属于集合1，部分属于集合2，提供每个城市所属的集合，现要求从城市1出发去城市2，要求途径的路中最多出现一条其两端城市不属于同一个集合 的路，求出符合该条件下的从城市1到城市2的最短路，若不存在符合条件的路，输出-1
注：数据中城市1必定属于集合1，城市2必定属于集合2
分析：由于城市1与城市2所属的集合固定，故在路径中必定有一条而且只能有一条路从属于集合 1的城市出发进入城市2，而定不会出现从集合2走向集合1的城市。 如此，M条路中凡是连接属于不同集合的城市的路为单向路，只能从集合1中的城市走向集合2, 在此基础上用Dijkstra算法求最短路即可。
就是分析出来，遍历图中的所有的双向边，但凡双向边的两个顶点是不同的，那么就把这条边改为从集合1指向集合2的边。然后用dijkstra就行。
#include<iostream>
#include<cstring>
#define inf 0x3f3f3f3f
#define maxn 10010
using namespace std;
typedef long long ll;
ll ans=0,n,m,s,e;
ll lowcost[maxn],mp[maxn][maxn],vis[maxn],leader[maxn];
void dijkstra(ll s){
for(int i=1;i<=n;i++){
lowcost[i]=mp[s][i];}vis[s]=1;lowcost[s]=0;for(int i=1;i<n;i++){
int v=-1;int minn=inf;for(int j=1;j<=n;j++){
if(!vis[j]&&lowcost[j]<minn){
minn=lowcost[j];v=j;}}if(v==-1) break;vis[v]=1;for(int j=1;j<=n;j++){
if(!vis[j]&&lowcost[v]+mp[v][j]<lowcost[j]){
lowcost[j]=lowcost[v]+mp[v][j];}}}
}
int main(){
std::ios::sync_with_stdio(false);while(cin>>n){
if(n==0) break;cin>>m;memset(vis,0,sizeof(vis));memset(leader,0,sizeof(leader));for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++){
mp[i][j]=inf;}mp[i][i]=0;}for(int i=0;i<m;i++){
int x,y,z;cin>>x>>y>>z;if(mp[x][y]>z){
mp[x][y]=mp[y][x]=z;}}for(int i=1;i<=n;i++){
int t;cin>>t;leader[i]=t;}//遍历该图，把两边领导不同的改为单向边//肯定不会出现从集合2走向集合1，应为只能转换一次for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(mp[i][j]!=inf&&leader[i]!=leader[j]){
if(leader[i]==1){
mp[j][i]=inf;}else{
mp[i][j]=inf;}}}}dijkstra(1);int pos=0;for(int i=1;i<=n;i++){
if(leader[i]==2){
pos=2;break;}}if(lowcost[pos]==inf) {
cout<<"-1"<<endl;}else {
cout<<lowcost[pos]<<endl;}}return 0;
}