详细题解参考：http://blog.csdn.net/lyy289065406/article/details/6689310
但是我认为一个点最多可以经过5次（因为10条边，看下图），而不是大部分题解说的3次。但是这个题的测试数据，2次到7次都可以过。
把边中的数据稍微改一改类似于这组数据：
7 10
1 2 1 1 1
2 3 2 1 1
3 2 3 1 1
2 4 3 1 99999999
4 2 4 1 1
2 5 4 1 99999999
5 2 5 1 1
2 6 5 1 99999999
6 2 6 1 1
2 7 6 1 99999999
AC代码：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cstdio>
using namespace std;
const int INF = 0x3f3f3f3f;
int n, m, Mincost;//城市数, 道路数, 最小总花费
int vist[11];//记录城市的访问次数,每个城市最多经过5次
struct Road
{int u, v, pre, w1, w2;
}road[11];
void dfs(int u, int fee) //u:当前所在城市,fee:当前方案的费用
{if(u == n && fee < Mincost){Mincost = fee;return ;}for(int i = 0; i < m; i++) //枚举道路{if(u == road[i].u && vist[u] <= 5){int v = road[i].v;vist[v]++;if(vist[road[i].pre])dfs(v, fee + road[i].w1);elsedfs(v, fee+road[i].w2);vist[v]--; //回溯}}
}
int main()
{while(cin >> n >> m){memset(vist, 0, sizeof(vist));vist[1] = 1; //从城市1出发，因此预记录到达1次Mincost = INF;for(int i = 0; i < m; i++)cin >> road[i].u >> road[i].v >> road[i].pre >> road[i].w1 >> road[i].w2;dfs(1, 0);if(Mincost == INF)cout << "impossible\n";elsecout << Mincost << endl;}return 0;
}
C++面向对象写法：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cstdio>
using namespace std;
const int INF = 0x3f3f3f3f;
class Road
{public:int u, v, pre, w1, w2;
};
class info
{public:info():Mincost(INF)//C++的'='和'()'都能赋值{ //但构造函数这里只能用'()'road = new Road[11];vist = new int[11];memset(vist, 0, sizeof(int)*11); //注意指针一定要这样用memsetvist[1] = 1; //从城市1出发，因此预记录到达1次}~info(){delete[] road;delete[] vist;}void input(void); //在类内对成员函数进行声明void output(void);void dfs(int u, int fee);protected:int n, m, Mincost;int *vist;Road *road;
};
void info::input(void)
{cin >> n >> m;for(int i = 0; i < m; i++)cin >> road[i].u >> road[i].v >> road[i].pre >> road[i].w1 >> road[i].w2;return ;
}
void info::output(void)
{if(Mincost == INF)cout << "impossible\n";elsecout << Mincost << endl;return ;
}
void info::dfs(int u, int fee)
{if(u == n && fee < Mincost){Mincost = fee;return ;}for(int i = 0; i < m; i++) //枚举道路{if(u == road[i].u && vist[u] <= 5){int v = road[i].v;vist[v]++;if(vist[road[i].pre])dfs(v, fee + road[i].w1);elsedfs(v, fee+road[i].w2);vist[v]--; //回溯}}
}
int main()
{info poj3411;poj3411.input();poj3411.dfs(1,0);poj3411.output();return 0;
}