问题描述
农夫约翰正在针对一个新区域的牛奶配送合同进行研究。他打算分发牛奶到T个城镇（标号为1..T），这些城镇通过R条标号为（1..R）的道路和P条标号为（1..P）的航路相连。
每一条公路i或者航路i表示成连接城镇Ai（1<=A_i<=T）和Bi（1<=Bi<=T）代价为Ci。每一条公路，Ci的范围为0<=Ci<=10,000；由于奇怪的运营策略，每一条航路的Ci可能为负的，也就是-10,000<=Ci<=10,000。
每一条公路都是双向的，正向和反向的花费是一样的，都是非负的。
每一条航路都根据输入的Ai和Bi进行从Ai->Bi的单向通行。实际上，如果现在有一条航路是从Ai到Bi的话，那么意味着肯定没有通行方案从Bi回到Ai。
农夫约翰想把他那优良的牛奶从配送中心送到各个城镇，当然希望代价越小越好，你可以帮助他嘛？配送中心位于城镇S中（1<=S<=T）。
输入格式
输入的第一行包含四个用空格隔开的整数T，R，P，S。
接下来R行，描述公路信息，每行包含三个整数，分别表示Ai，Bi和Ci。
接下来P行，描述航路信息，每行包含三个整数，分别表示Ai，Bi和Ci。
输出格式
输出T行，分别表示从城镇S到每个城市的最小花费，如果到不了的话输出NO PATH。
样例输入
6 3 3 4
1 2 5
3 4 5
5 6 10
3 5 -100
4 6 -100
1 3 -10
样例输出
NO PATH
NO PATH
5
0
-95
-100
数据规模与约定
对于20%的数据，T<=100，R<=500，P<=500；
对于30%的数据，R<=1000，R<=10000，P<=3000；
对于100%的数据，1<=T<=25000，1<=R<=50000，1<=P<=50000。
解答：主要运用深度优先搜索和权值约束。相关知识参见http://blog.163.com/zhoumhan_0351/blog/static/3995422720098342257387/
下面有两个程序可供参考
实现的Java算法如下
（由于采用递归，在测试大规模数据时会报java.lang.*Error错误。）
import java.util.Scanner;
import java.util.Stack;
public class MinCost {
static Stack<Integer> stack = new Stack<Integer>();//堆栈
static Stack<Integer> cost = new Stack<Integer>();//花费的堆栈
static int temp =0;
public static void main(String []args)
{
Scanner ss = new Scanner(System.in);
int T = ss.nextInt();
int min[] = new int[T+1];
int parents[] = new int[T+1];
int R = ss.nextInt();
int P = ss.nextInt();
int S = ss.nextInt();
int A[] = new int[2*R+P+1];
int B[] = new int[2*R+P+1];
int C[] = new int[2*R+P+1];
int a,b,c;
for(int i=1;i<=T;i++)//访问标志初始化
{
parents[i] = 0;
}
for(int i=1;i<=2*R;i++)
{
a = ss.nextInt();
b = ss.nextInt();
c = ss.nextInt();
A[i] = a;B[i] = b;C[i] = c;
i++;
A[i] = b;B[i] = a;C[i] = c;
}
for(int i=2*R+1;i<=2*R+P;i++)
{
A[i] = ss.nextInt();
B[i] = ss.nextInt();
C[i] = ss.nextInt();
}
stack.push(S);//将出发城镇初始化
min[S] = 0;
cost.push(0);
int mini[] = DFS(A,B,C,min,parents);
for(int i=1;i<mini.length;i++)
{
if(i!=S&&mini[i]==0)
System.out.println("NOPATH");
else
System.out.println(mini[i]);
}
}
public static int[] DFS(int[] A,int[] B ,int[] C,int[] min,int[] parents)
{
for(int i=1;i<A.length;i++)
{
if(A[i]==stack.peek()&&checkParents(B[i],parents)&&check(B[i]))
{
stack.push(B[i]);
cost.push(cost.peek()+C[i]);
parents[stack.peek()] = A[i];
if(min[B[i]]==0||min[B[i]]>cost.peek())
{
min[B[i]] = cost.peek();
}
DFS(A,B,C,min,parents);
}
}
if(stack.peek()==stack.get(0))
return min;
cost.pop();
stack.pop();
DFS(A,B,C,min,parents);
return min;
}
public static boolean check(int n)
{
boolean flag = true;
for(int i=0;i<stack.size();i++)
{
if(n==stack.get(i))
{
flag = false;
break;
}
}
return flag;
}
public static boolean checkParents(int n,int[] parents)
{
if(parents[n]==stack.peek())
return false;
else
return true;
}
}
非递归程序（木有大量测试数据）
import java.util.Scanner;
import java.util.Stack;
public class TT {
public static int S;
public static void main(String []args)
{
int minx[] = DFS();
for(int i=1;i<minx.length;i++)
{
if(i!=S&&minx[i]==0)
System.out.println("NO PATH");
else
System.out.println(minx[i]);
}
}
public static int[] DFS()
{
Scanner ss = new Scanner(System.in);
int T = ss.nextInt();//输入城市数
int R = ss.nextInt();//输入道路数
int P = ss.nextInt();//输入航路数
S = ss.nextInt();//输入出发城镇
int min[] = new int[T+1];//记录到每个城镇的最小花费
int C[][] = new int[T+1][T+1];//C[i][j]表示记录从i城镇到j城镇的花费
boolean visit[] = new boolean[T+1];//标记每个城市是否被访问过
Stack<Integer> stack = new Stack<Integer>();//堆栈
Stack<Integer> cost = new Stack<Integer>();//花费的堆栈
int temp =0;
Stack<Integer>[] city = new Stack[T+1];//记录每个每个城镇为出发点的所有道路或航路
int flag[] = new int[T+1];//记录该城镇为访问节点为i时的下一个访问节点在city[]中的位置
for(int i=1;i<city.length;i++)//将city[]数组初始化
{
city[i] = new Stack<Integer>();
}
for(int i=1;i<visit.length;i++)//将visit[]数组初始化
for(int j=1;j<visit.length;j++)
{
visit[i] = false;
}
int m,n,k;
for(int i=1;i<=R;i++)//将city[]数组赋值
{
m = ss.nextInt();
n = ss.nextInt();
k = ss.nextInt();
city[m].add(n);C[m][n]=k;
city[n].add(m);C[n][m]=k;
}
for(int i=1;i<=P;i++)//将city[]数组赋值
{
m = ss.nextInt();
n = ss.nextInt();
k = ss.nextInt();
city[m].add(n);C[m][n]=k;
}
stack.push(S);//将出发城镇压入堆栈
min[S] = 0;//将出发城镇的最小花费置0
cost.push(0);//花费初始压入0
visit[S] = true;//将出发城镇访问位置true
/*
* 由深度优先搜索对所有路径进行遍历
*/
int i;
while(true)
{
while(true)
{
int a = stack.peek();//取出访问节点
for(i=flag[a];i<city[a].size();i++)//在city[]遍历访问
{
int b =city[a].get(i);
if(!visit[b])//判断下一个节点是否被访问过
{
/*
* 如果下个节点可被访问。则将相应数据压入堆栈.并把被城镇的city[]数组的访问位flag[]+1
*/
cost.push(cost.peek()+C[a][b]);//将到下一个节点所需花费压入cost堆栈
flag[a]++;
visit[b] = true;
stack.push(b);
int c = stack.peek();
System.out.println(c+" "+min[c]+" "+cost.peek());
if(min[c]==0||min[c]>cost.peek())//判断是否到该访问节点是否是已有路径到该节点的最小花费
{
min[c] = cost.peek();
}
break;//退出 ,进去下一个节点的访问
}
}
if(i==city[a].size())
break;//如果遍历该节点的city[]数组，都没有可访问的下一个节点则退出，进行回退操作
}
/*
* 如果没有找到下一个节点。则回退，相应数据出栈
*/
int d = stack.peek();
if(d==stack.get(0))//如果将要出栈数据为出发城镇则遍历结束。退出。
break;
visit[d]=false;
cost.pop();
stack.pop();
}
return min;
}
}