Part1:回顾

1.最短路径问题

首先看下最短路径问题的描述。

这类问题也可以分为两类，分别是单源和多源。

首先来看下单源的问题，这里也可以分为两种，分别为无权和有权的情形。
无权图的情形其实就是数距离原点的步数，这样的话就可以使用上一讲使用的BFS算法。

有权图的情形使用了贪心算法，从源点开始，每一步找到已访问节点至未访问节点的最短路径，将这条路径及顶点包括在已访问的节点中具体如下。

最后来看一下多源最短路算法，其实就是个三重循环。

Part2:作业

作业1

07-图4 哈利·波特的考试（25 分）
哈利·波特要考试了，他需要你的帮助。这门课学的是用魔咒将一种动物变成另一种动物的本事。例如将猫变成老鼠的魔咒是haha，将老鼠变成鱼的魔咒是hehe等等。反方向变化的魔咒就是简单地将原来的魔咒倒过来念，例如ahah可以将老鼠变成猫。另外，如果想把猫变成鱼，可以通过念一个直接魔咒lalala，也可以将猫变老鼠、老鼠变鱼的魔咒连起来念：hahahehe。
现在哈利·波特的手里有一本教材，里面列出了所有的变形魔咒和能变的动物。老师允许他自己带一只动物去考场，要考察他把这只动物变成任意一只指定动物的本事。于是他来问你：带什么动物去可以让最难变的那种动物（即该动物变为哈利·波特自己带去的动物所需要的魔咒最长）需要的魔咒最短？例如：如果只有猫、鼠、鱼，则显然哈利·波特应该带鼠去，因为鼠变成另外两种动物都只需要念4个字符；而如果带猫去，则至少需要念6个字符才能把猫变成鱼；同理，带鱼去也不是最好的选择。

输入格式:
输入说明：输入第1行给出两个正整数N (≤100)和M，其中N是考试涉及的动物总数，M是用于直接变形的魔咒条数。为简单起见，我们将动物按1~N编号。随后M行，每行给出了3个正整数，分别是两种动物的编号、以及它们之间变形需要的魔咒的长度(≤100)，数字之间用空格分隔。

输出格式:
输出哈利·波特应该带去考场的动物的编号、以及最长的变形魔咒的长度，中间以空格分隔。如果只带1只动物是不可能完成所有变形要求的，则输出0。如果有若干只动物都可以备选，则输出编号最小的那只。

输入样例:
6 11
3 4 70
1 2 1
5 4 50
2 6 50
5 6 60
1 3 70
4 6 60
3 6 80
5 1 100
2 4 60
5 2 80

输出样例:
4 70

这题的意思其实就是求任意两点的最短路径，所以使用Floyd算法,这里给了python和c语言版，因为python会超时。

python版本

# -*- coding: utf-8 -*-
"""
Created on Mon Apr 23 12:08:54 2018

@author: 715073608
"""

#读入点和边的个数
a=map(int,raw_input().strip().split())
n=a[0]
l=a[1]

#初始矩阵
b=[[float('Inf') for j in range(n)] for i in range(n)]

#读入数据
for i in range(l):
    temp=map(int,raw_input().strip().split())
    b[temp[0]-1][temp[1]-1]=temp[2]
    b[temp[1]-1][temp[0]-1]=temp[2]

#弗洛伊德算法
for k in range(n):
    for i in range(n):
        for j in range(n):
            if(i!=j and b[i][k]+b[k][j]<b[i][j]):
                b[i][j]=b[i][k]+b[k][j]
            if (i==j):
                b[i][i]=0
#定义最大值
def findmax(x):
    k=0
    l=0
    for i in range(len(x)):
        if x[i]>l:
            l=x[i]
            k=i
    return l,k

#index=[]
leng=[]
flag=0
for i in b:
    l=max(i)
    k=i.index(l)
    if l==float('inf'):
        flag=1
        break
    else:
        leng.append(l)

if flag:
    print('0')
else:
    l=min(leng)
    k=leng.index(l)
    print(str(k+1)+' '+str(l))

c语言版本

#include <stdio.h>
#define max 100000
int findmax(int x[],int l);

int main(){
	//读入点和边的个数 
	int n,l;
	scanf("%d%d",&n,&l);
	
	//初始矩阵
	int b[n][n];
	for (int i=0;i<n;i++){
		for (int j=0;j<n;j++){
			b[i][j]=max;
		}
	}
	
	//读入数据
	for (int i=0;i<l;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		b[x-1][y-1]=z;
		b[y-1][x-1]=z;
	}
	
	//弗洛伊德算法
	for (int k=0;k<n;k++){
		for (int i=0;i<n;i++){
			for (int j=0;j<n;j++){
				if (i!=j and b[i][k]+b[k][j]<b[i][j]){
					b[i][j]=b[i][k]+b[k][j];
				}
				if (i==j){
					b[i][i]=0;
				}
			}
		}
	}
	
	//找每行最大值
	int leng[n];
	int flag=0;
	for (int i=0;i<n;i++){
		int l=findmax(b[i],n);
		if (l==max){
			flag=1;
			break;
		}else{
			leng[i]=l;
		}
	}
	
	//输出 
	if (flag==1){
		printf("0");
	}else{
		int l=leng[0];
		int k=0;
		for (int i=0;i<n;i++){
			if (leng[i]<l){
				l=leng[i];
				k=i;
			}
		}
		printf("%d %d",k+1,l);
	}
	return 0;
} 

int findmax(int x[],int l){
	int h=0;
	for (int i=0;i<l;i++){
		if (x[i]>h){
			h=x[i];
		}			
	}
	return h;
}

作业2

07-图5 Saving James Bond - Hard Version（30 分）
This time let us consider the situation in the movie “Live and Let Die” in which James Bond, the world’s most famous spy, was captured by a group of drug dealers. He was sent to a small piece of land at the center of a lake filled with crocodiles. There he performed the most daring action to escape — he jumped onto the head of the nearest crocodile! Before the animal realized what was happening, James jumped again onto the next big head… Finally he reached the bank before the last crocodile could bite him (actually the stunt man was caught by the big mouth and barely escaped with his extra thick boot).
Assume that the lake is a 100 by 100 square one. Assume that the center of the lake is at (0,0) and the northeast corner at (50,50). The central island is a disk centered at (0,0) with the diameter of 15. A number of crocodiles are in the lake at various positions. Given the coordinates of each crocodile and the distance that James could jump, you must tell him a shortest path to reach one of the banks. The length of a path is the number of jumps that James has to make.

Input Specification:
Each input file contains one test case. Each case starts with a line containing two positive integers N (≤100), the number of crocodiles, and D, the maximum distance that James could jump. Then N lines follow, each containing the (x,y) location of a crocodile. Note that no two crocodiles are staying at the same position.

Output Specification:
For each test case, if James can escape, output in one line the minimum number of jumps he must make. Then starting from the next line, output the position (x,y) of each crocodile on the path, each pair in one line, from the island to the bank. If it is impossible for James to escape that way, simply give him 0 as the number of jumps. If there are many shortest paths, just output the one with the minimum first jump, which is guaranteed to be unique.

Sample Input 1:
17 15
10 -21
10 21
-40 10
30 -50
20 40
35 10
0 -10
-25 22
40 -40
-30 30
-10 22
0 11
25 21
25 10
10 10
10 35
-30 10

Sample Output 1:
4
0 11
10 21
10 35

Sample Input 2:
4 13
-12 12
12 12
-12 -12
12 -12

Sample Output 2:
0

这题是之前做过的题目的加强版，这里是判断最少需要几步，有几个点需要注意，一是首先要判断是否能跳到岸边，二是岛内和岸边的鳄鱼不要访问。

# -*- coding: utf-8 -*-
"""
Created on Mon Apr 23 22:38:53 2018

@author: Administrator
"""
#定义点的距离
def dis1(x,y):
    return ((x[0]-y[0])**2+(x[1]-y[1])**2)**0.5

#定义离岸的距离
def dis2(x):
    return min(abs(x[0]-50),abs(x[0]+50),abs(x[1]-50),abs(x[1]+50))

def dis3(x):
    return abs(x[0])<=50 and abs(x[1])<=50


#读入鳄鱼个数n,以及跳跃距离d
n,d=map(int,raw_input().strip().split(' '))

#初始化图，注意增加原点
m=[[0,0]]

#读入数据
for i in range(n):
    temp=map(int,raw_input().strip().split(' '))
    #不在岛上和岸边的鳄鱼才算在内
    if dis1([0,0],temp)>=7.5 and dis3(temp):
        m.append(temp)

#有效鳄鱼个数
n=len(m)-1

#构造邻接表
s=[[] for i in range(n+1)]

#初始原点及其相邻点,第一个点为离原点最近的点
#step1读入距离
dis={}
for i in range(1,n+1):
    if dis1([0,0],m[i])<=d+7.5:
        dis[i]=dis1([0,0],m[i])

#step2找按距离从小到大排序,为了输出唯一
x=sorted(dis.items(),key=lambda item:item[1])

#step3将其余的点读入数组
for i in x:
    s[0].append(i[0])

#初始其余的节点,注意不取在岸边的鳄鱼
for i in range(1,n+1):
    for j in range(n+1):
        if i!=j and dis1(m[i],m[j])<=d:
            s[i].append(j)

#初始化访问矩阵，0表示未访问
y=[0 for i in range(n+1)]
y[0]=1

#定义BFS
#s为图，m为对应点，x为开始节点,y为访问数组，记录是否访问过,s用来返回结果,q为程序中需要的队列
def BFS(s,m,x,y):
    path=[-1 for j in range(n+1)]
    #记录是否到岸
    flag=0
    q=[]
    y[x]=1
    q.append(x)
    while(len(q)>0):
        v=q.pop(0)
        path.append(v)
        for i in s[v]:
            if y[i]==0:
                y[i]=1
                q.append(i)
                path[i]=v
                q.append(i)
                if dis2(m[i])<=d:
                    flag=1
                    return flag,path,i
    return flag,path,i

#能跳到第二个点
if len(s[0])>0:
    a,b,c=BFS(s,m,0,y)
#不能跳到第二个点
else:
    a=0

if a==0:
    print a
#一步跳
elif d>=50-7.5:
    print 1
else:
    u=c
    i=1
    ans=[]
    while(u!=0):
        ans.append(m[u])
        u=b[u]
        i+=1
    ans.reverse()
    print i
    for j in ans:
        print str(j[0])+' '+str(j[1])

作业3

07-图6 旅游规划（25 分）
有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。

输入格式:
输入说明：输入数据的第1行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0~(N−1)；M是高速公路的条数；S是出发地的城市编号；D是目的地的城市编号。随后的M行中，每行给出一条高速公路的信息，分别是：城市1、城市2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过500。输入保证解的存在。

输出格式:
在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。

输入样例:
4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20

输出样例:
3 40

这题看起来类似Dijkstra算法，但是变形一下，不过这里使用了一个投机取巧的方法，给路径一个很大的权重，保证路径小的时候总花费一定小。这里依旧使用了python和c来实现，因为python会超时。

python版本

# -*- coding: utf-8 -*-
"""
Created on Wed Apr 25 12:15:43 2018

@author: 715073608
"""

n,m,s,d=map(int,raw_input().strip().split())

#读入数据，存入字典
v={}
for i in range(n):
    v[i]={}

for j in range(m):
    a,b,c,e=map(int,raw_input().strip().split())
    #v[a][b]=(c,d)
    #v[b][a]=(c,d)
    v[b][a]=c*10**10+e
    v[a][b]=c*10**10+e

#记录未访问的节点
y=set(range(n))
#记录dist
x=[10**15 for i in range(n)]

#找到未收录顶点中dist最小者
def findmin(a,b):
    #记录最先的边长
    l=10**15
    #记录最小边对应的顶点
    m=-1
    for i in b:
        if a[i]<l:
            l=a[i]
            m=i
    return m

m={}
for i in range(n):
    m[i]=10**15
m[s]=0

while True:
    k=findmin(m,y)
    if k==-1:
        break
    y.remove(k)
    for j in v[k]:
        if j in y:
            if m[k]+v[k][j]<m[j]:
                m[j]=m[k]+v[k][j]
                #path[j]=k
print m[d]/(10**10),m[d]%(10**10)

C语言版本

#include <stdio.h>

int findmin(long long a[],int b[],int n);

int main(){
	int n,m,s,d;
	scanf("%d %d %d %d",&n,&m,&s,&d);
	
	long long v[n][n];
	//初始化
	for (int i=0;i<n;i++){
		for (int j=0;j<n;j++){
			v[i][j]=0;
		}
	} 
	
	//读入数据,将边长给一个很大的权重，这样一次排序即可。 
	int a,b,c,e;
	for (int i=0;i<m;i++){
		scanf("%d %d %d %d",&a,&b,&c,&e);
		v[a][b]=c*10000000000+e;
		v[b][a]=c*10000000000+e;
	}
	
	//记录是否访问过
	int y[n]={0};

	//记录dist
	long long p[n];
	for (int i=0;i<n;i++){
		p[i]=1000000000000000;
	}
	p[s]=0;
	
	while (1){
		int k=findmin(p,y,n);
		if (k==-1){
			break;
		}
		y[k]=1;
		for (int j=0;j<n;j++){
			//未访问且有边相连 
			if (y[j]==0&&v[k][j]>0){
				if (p[k]+v[k][j]<p[j]){
					p[j]=p[k]+v[k][j];
				}
			}
		}
	}
	printf("%d %d",p[d]/10000000000,p[d]%10000000000);
}

int findmin(long long a[],int b[],int n){
	long long l=1000000000000000;
	int m=-1;
	for (int i=0;i<n;i++){
		if (b[i]==0 && a[i]<l){
			l=a[i];
			m=i;
		}
	}
	return m;
}