首页 > 试题广场 >

最短送餐路程计算

[编程题]最短送餐路程计算

热度指数：425 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

美团外卖是知名的外卖平台，现在有一名新入职的外卖小哥。请你给他写一段程序根据外卖地图和交通拥堵情况，告诉他从“配送点”V0，到各个目的地的最短配送距离。其中拥堵程度可以与路径参数直接相加，例如：V0点拥堵，拥堵系数是2，那么在地图上V0点的3条线路的参数都要加2，由原来的1、2、7变为3、4、9再进行。

路径规划计算。路径参数越大代表路程越长。

输入描述:

输入数据只有一行，有三个int型参数，分别表示：目的地编号、拥堵节点编号和拥堵值。

例如：4 3 1，代表目的地是V4，在V3节点有拥堵情况，拥堵系数是1。

输出描述:

输出一个数字表示有起点V0到终点的最短距离

示例1

输入

4 2 1

输出

示例2

输入

5 4 1

输出

算法知识视频讲解

Java

牛客35031561号

import java.util.*;
public class Main {
    static int dijkstra(int[][] g, int n, int target, int k, int value){
        boolean[] finished = new boolean[n];
        int[] distance = new int[n];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[0] = k == 0 ? value : 0;
        if(k != 0) {
            for(int i=0; i < n; i++)
                if(i != k && g[k][i] != -1) {
                    g[i][k] = g[k][i] += value;
                }
        }
        for(int i=0; i < n; i++) {
            int t = -1;
            for(int j=0; j < n; j++) {
                if(finished[j]==false &&(t == -1 || distance[t] > distance[j])) {
                   t = j;
                }
            }
            finished[t] = true;
            for(int j=0; j < n; j++) {
                if(g[t][j] != -1) {
                    distance[j] = Math.min(distance[j], distance[t]+g[t][j]);
                }
            }

        }
        return distance[target];
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int target = sc.nextInt();
        int k = sc.nextInt(), value=sc.nextInt();
        int n = 6;
        int[][] g = new int[n][n];
        for(int i=0; i < n; i++){
            Arrays.fill(g[i], -1);
            g[i][i] = 0;
        }
        g[0][1] = 1; g[0][2] = 2; g[0][3] = 7;
        g[1][0] = 1; g[1][2] = 2; g[1][4] = 5; g[1][5] = 4;
        g[2][0] =  2; g[2][1] = 2; g[2][4] = 4; g[2][3] = 4;
        g[3][0] = 7; g[3][2] = 4; g[3][4] = 6;
        g[4][1] = 5; g[4][2] = 4; g[4][3] = 6; g[4][5] = 3;
        g[5][1]=4; g[5][4] = 3;
        System.out.println(dijkstra(g, n, target, k, value));
    }
}

发表于 2020-07-12 19:50:51 回复(0)

巴德--

def f(t,v,c):
a = [0, 1, 2, 6, 6, 5]
if v == 0:
for i in range(1, 6):
a[i] += c
if v == 1:
a[1] += c
a[5] += c * 2
a[5] = min(a[5], 9)
if v == 2:
a[4] += c * 2
a[4] = max(a[4],6)
a[3] += c * 2
a[3] = max(a[3],7)
a[2] += c
if v == 3:
a[3] += c
if v == 4:
a[4] += c
if v == 5:
a[5] += c
print(a[t])

if __name__ == "__main__":
i = input().split(" ")
for t in range(len(i)):
i[t] = int(i[t])
f(i[0], i[1], i[2])

发表于 2020-08-09 14:09:19 回复(0)

冰糖雪梨ls

100%通过，python

# dijksta算法
class Solution:
    '''
    输入：邻接矩阵，
    输出，源点V0到各点的最小距离
    '''
    def Dijkstr(self,graph,v0):
        # final 保存已经遍历过的点，d保存最短路径
        n=len(graph)
        final,D=[0]*n,[0]*n
        for i in range(0,n):
            D[i]=graph[v0][i]
        D[v0]=0
        final[v0]=1
        for v in range(1,n):
            min = float("Inf")
            for w in range(0,n):
                if final[w]==0 and D[w]<min:
                    k=w
                    min=D[w]
            final[k]=1
            for w in range(0,n):
                if final[w]==0 and min +graph[k][w]<D[w]:
                    D[w]=min +graph[k][w]
        return D

s = Solution()
aim,crowd,exp=map(int,input().split())

graph=[
[0,1,2,7,9999,9999],
[1,0,2,9999,5,4],
[2,2,0,4,4,9999],
[7,9999,4,0,6,9999],
[9999,5,4,6,0,3],
[9999,4,9999,9999,3,0]
]
for i in range(0,len(graph)):
    for j in range(0,len(graph)):
        if i==crowd&nbs***bsp;j==crowd:
            graph[i][j]+=exp
print(s.Dijkstr(graph,0)[aim])

编辑于 2020-04-18 19:09:06 回复(0)

牛客157007370号

inf =9999

m=[

[0,1,2,7,inf,inf],

[1,0,2,inf,5,4],

[2,2,0,4,4,inf],

[7,inf,4,0,6,inf],

[inf,5,4,6,0,3],

[inf,4,inf,inf,3,0]

]

a,b,c=map(int,input().split())

fori inrange(6):

m[b][i]+=c

m[i][b]+=c

fork inrange(6):

fori inrange(6):

forj inrange(6):

ifm[i][j]>m[i][k]+m[k][j]:

m[i][j]=m[i][k]+m[k][j]

print(m[0][a])

发表于 2020-03-26 18:36:58 回复(0)

不想改也得改了

bfs+状态压缩

while(1):
    line = input().strip()
    if len(line)<=0:break
    line = line.split(' ')
    target_id,busy_id,busy_val= int(line[0]),int(line[1]),int(line[2])
    #e.g.: 4,2,1 代表目的地:V4, 拥堵结点：2, 拥堵程度：1
    max_N = 9999999
    map = [[] for _ in range(6)]
    map[0] = [0,1,2,7,max_N,max_N]
    map[1] = [1,0,2,max_N,5,4]
    map[2] = [2,2,0,4,4,max_N]
    map[3] = [7,max_N,4,0,6,max_N]
    map[4] = [max_N,5,4,6,0,3]
    map[5] = [max_N,4,max_N,max_N,3,0]

    for i in range(6):
        map[busy_id][i]+=busy_val
    for i in range(6):
        if i!=busy_id:map[i][busy_id]+=busy_val
        
    #bfs+状压
    def bfs(node,mask):
        if node==target_id:return 0
        min_step = float('inf')
        for i in range(6):
            if node!=i and map[node][i]<max_N and mask&(2**i)==0:
                min_step = min(min_step,bfs(i,mask|(2**i))+map[node][i])
        return min_step

    print(bfs(0,0))

一定一定不要忘了：其他的节点也要增加和拥堵结点的距离，我就是因为这个最后没过

发表于 2023-07-25 22:39:00 回复(0)

一只花花牛

《通信网络基础》算法之 - F算法

target, node, jamSize = map(int, input().split())
curMap = [[0,1,2,7,99,99], [1,0,99,99,5,4], [2,99,99,4,4,99], 
          [7,99,4,99,6,99], [99,5,4,6,99,3], [99,4,99,99,3,99]]
for a in range(6):
    curMap[a][node] = curMap[node][a] = curMap[node][a] + jamSize
for c in range(6):
    for i in range(6):
        for j in range(i+1, 6):
            curMap[j][i] = curMap[i][j] = min(curMap[i][j], curMap[i][c] + curMap[c][j])
print(curMap[0][target])

发表于 2021-07-26 10:09:44 回复(0)