2013
12-12

# 九度-1008-最短路径问题[解题代码]

(1<n<=1000, 0<m<100000, s != t)

3 2
1 2 5 6
2 3 4 5
1 3
0 0

9 11

java 代码如下：
import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Scanner;
public class Main{
static int arr[][];
static int cost[][];
static int dist[];
static int money[];
static boolean isOK[];
static int n;
static int m;
static final int  MAX = Integer.MAX_VALUE;
public static void main(String[] args) {
Scanner s = new Scanner(new BufferedInputStream(System.in));
while(s.hasNextInt()){
n = s.nextInt();
m = s.nextInt();
if(n==0 && m==0)
break;
arr = new int[n][n];
cost = new int[n][n];
dist = new int[n];
money = new int[n];
isOK = new boolean[n];
for(int[] a:arr)
Arrays.fill(a, MAX);
for(int[] a:cost)
Arrays.fill(a, MAX);
for(int i=0; i<m; i++){
int a = s.nextInt()-1;
int b = s.nextInt()-1;
int c = s.nextInt();
int d = s.nextInt();
if(c < arr[a][b] ){ //如果有更小的路径  则更新
arr[a][b] = c;
arr[b][a] = c;
cost[a][b] = d;
cost[b][a] = d;
}
if( c == arr[a][b] && d<cost[a][b]){
cost[a][b] = d;
cost[b][a] = d;
}
}
//			for(int[] a:arr){
//				for(int aa:a)
//					System.out.print(aa+" ");
//				System.out.println();
//			}
int start = s.nextInt()-1;
int end = s.nextInt()-1;
if(start == end)
System.out.println("0 0");
dij(start,end);
System.out.println(dist[end]+" "+money[end]);

}
}
static void dij(int start,int end){
for(int i=0; i<n; i++){
dist[i] = arr[start][i];  //初始化dist
money[i] = cost[start][i];
}
int index = start;
for(int i=0; i<n; i++){  //外层循环，依次找出到各个点的最短距离
if(i==start)
continue;
int min = MAX;
for(int j=0; j<n; j++)
if(!isOK[j] && dist[j] < min){  //找到最短路径的顶点
min = dist[j];
index = j;
}
isOK[index] = true;
//			if(isOK[end])
//				break;

for(int k=0; k<n; k++){  //更新 dist[] 和  money[]
if(k==start)
continue;
if( !isOK[k] && arr[index][k] != MAX){
int temp = arr[index][k]+dist[index];
int temp2 =cost[index][k] + money[index];
if(temp < dist[k]){
dist[k] = temp;
money[k] = temp2;
}else if(temp == dist[k] && (money[k] > temp2)){
money[k] = temp2;
}

}
}

}
}

}

/**************************************************************
Problem: 1008
User: coder
Language: Java
Result: Accepted
Time:760 ms
Memory:32956 kb
****************************************************************/

1. 第2题，TCP不支持多播，多播和广播仅应用于UDP。所以B选项是不对的。第2题，TCP不支持多播，多播和广播仅应用于UDP。所以B选项是不对的。

2. #include <cstdio>

int main() {
//answer must be odd
int n, u, d;
while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
if(n<=u) { puts("1"); continue; }
n-=u; u-=d; n+=u-1; n/=u;
n<<=1, ++n;
printf("%dn",n);
}
return 0;
}