Part2:作业

• 作业1

07-图4 哈利·波特的考试（25 分）

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

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

"""
#定义点的距离
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 分）

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

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;
}