首页 > 试题广场 >

牛牛取快递

[编程题]牛牛取快递

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

牛牛的快递到了，他迫不及待地想去取快递，但是天气太热了，以至于牛牛不想在烈日下多走一步。他找来了你，请你帮他规划一下，他最少要走多少距离才能取回快递。

输入描述:

每个输入包含一个测试用例。
输入的第一行包括四个正整数，表示位置个数N(2<=N<=10000)，道路条数M(1<=M<=100000)，起点位置编号S(1<=S<=N)和快递位置编号T(1<=T<=N)。位置编号从1到N，道路是单向的。数据保证S≠T，保证至少存在一个方案可以从起点位置出发到达快递位置再返回起点位置。
接下来M行，每行包含三个正整数，表示当前道路的起始位置的编号U(1<=U<=N)，当前道路通往的位置的编号V(1<=V<=N)和当前道路的距离D(1<=D<=1000)。

输出描述:

对于每个用例，在单独的一行中输出从起点出发抵达快递位置再返回起点的最短距离。

示例1

输入

输出

算法知识视频讲解

FlushHip

2018年校招全国统一模拟笔试(五月场)编程题集合 - 题解

https://blog.csdn.net/FlushHip/article/details/80446002

发表于 2018-05-25 02:56:45 回复(0)

Samuelyo

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

    public static class Item {
        int index;
        int weight;

        public Item(int index, int weight) {
            this.index = index;
            this.weight = weight;
        }
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int len = sc.nextInt();
            int times = sc.nextInt();
            int start = sc.nextInt();
            int end = sc.nextInt();
            List<List<Item>> lists = new ArrayList<List<Item>>();
            for (int i = 0; i <= len; i++) {
                lists.add(new ArrayList<Item>());
            }
            for (int i = 0; i < times; i++) {
                int s = sc.nextInt();
                int e = sc.nextInt();
                int v = sc.nextInt();
                lists.get(s).add(new Item(e, v));
            }
            int res = helper(lists, len, start, end) + helper(lists, len, end, start);
            System.out.println(res);
        }
        sc.close();

    }

    public static int helper(List<List<Item>> lists, int len, int start, int end) {
        boolean[] visited = new boolean[len + 1];
        int[] dis = new int[len + 1];
        Arrays.fill(dis, Integer.MAX_VALUE);
        dis[start] = 0;
        PriorityQueue<Item> queue = new PriorityQueue<Item>(new Comparator<Item>() {

            @Override
            public int compare(Item o1, Item o2) {
                return o1.weight - o2.weight;
            }

        });
        queue.offer(new Item(start, 0));
        while (!queue.isEmpty()) {
            Item item = queue.poll();
            int index = item.index;
            if (visited[index]) {
                continue;
            }
            visited[index] = true;
            List<Item> list = lists.get(index);
            for (int j = 0; j < list.size(); j++) {
                Item temp = list.get(j);
                if (!visited[temp.index] && dis[index] + temp.weight < dis[temp.index]) { 
                    dis[temp.index] = dis[index] + temp.weight;
                    queue.offer(new Item(temp.index, dis[index] + temp.weight));
                }
            }
        }
        return dis[end];
    }

}

发表于 2018-05-26 13:01:40 回复(0)

勇敢牛牛，不怕困难！

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define INF 0x3f3f3f3f
#define not !
#define and &&

typedef struct {
  int to;     // 邻接点的编号 
  int next;   // 下一个邻接点的下标
  int weight; // 邻接点的权重
} Edge;

void addEdge(int* head, Edge* edges, const int u, const int v, const int w, int idx) {
  (*(edges + idx)).next = *(head + u);
  (*(edges + idx)).to = v;
  (*(edges + idx)).weight = w;
  *(head + u) = idx; 
}

void printAdjList(const int n, int* head, Edge* edges) {
  int i, u, v, w;
  for (u = 1; u <= n; ++u) {
    fprintf(stdout, "vertex %d: [  ", u);
    for (i = *(head + u); i; i = (*(edges + i)).next) {
      v = (*(edges + i)).to, w = (*(edges + i)).weight; 
      fprintf(stdout, "(%d, %d)  ", v, w);
    }
    fputs("]\n", stdout);
  }
  fputc(10, stdout);
}
  
// 荷兰科学家-迪杰斯特拉算法
int dijkstra_algorithm(int* head, Edge* edges, const int n, int start, int target) {
  
  int dists[n + 1]; 
  int visited[n + 1];
  memset(dists, INF, sizeof dists);
  memset(visited, 0x0000, sizeof visited);
  *(dists + start) = 0; // 源点到源点的距离为0
  
  int i, t, u, v, w, min_dist, selected;
  for (t = 0; t < n - 1; ++t) {
    // step 1
    min_dist = INF, selected = -1;
    for (u = 1; u <= n; ++u) {
      if (not *(visited + u) and *(dists + u) < min_dist) {
        min_dist = *(dists + u);
        selected = u;
      }
    }
    
    // step 2 加入已选顶点集合
    if (selected == -1) break;
    *(visited + selected) = 1;
    
    // step 3 进行松驰操作 
    for (i = *(head + selected); i; i = (*(edges + i)).next) {
      v = (*(edges + i)).to, w = (*(edges + i)).weight; 
      if (*(visited + v)) continue;
      if (*(dists + selected) + w < *(dists + v))
        *(dists + v) = *(dists + selected) + w;
    }
  }
    
  return *(dists + target);
}

int main(const int argc, const char** argv) {
  int n, m, s, t;
  fscanf(stdin, "%d %d %d %d", &n, &m, &s, &t);
  
  int head[n + 1];
  Edge edges[m + 1]; // directed graph
  memset(head, 0x0000, sizeof head);
  
  int i, u, v, w;
  for (i = 1; i <= m; ++i) {
    fscanf(stdin, "%d %d %d", &u, &v, &w);
    addEdge(head, edges, u, v, w, i);
  }
  
  // printAdjList(n, head, edges);
  
  int dist = dijkstra_algorithm(head, edges, n, s, t) 
           + dijkstra_algorithm(head, edges, n, t, s);
  
  return fprintf(stdout, "%d", dist), 0;
}

发表于 2021-07-17 20:09:17 回复(0)

唉梅子



#include <iostream>
#include <vector>
#include <queue>
#include "assert.h"
using namespace std;
const int N = 10003;
const int INF = 0x3f3f3f3f;
int spfa(int src, int des, vector< pair<int> > mp[], int n)
{
	vector<int> dis(n + 1, INF);
	vector<bool> used(n + 1, false);
	queue<int> que({ src });
	dis[src] = 0;
	used[src] = true;
	while (!que.empty()) {
		auto u = que.front();
		que.pop();
		used[u] = false;
		for (auto it = mp[u].begin(); it != mp[u].end(); ++it) {
			auto v = it->first, w = it->second;
			if (dis[v] > dis[u] + w) {
				dis[v] = dis[u] + w;
				if (!used[v]) {
					used[v] = true;
					que.push(v);
				}
			}
		}
	}
	return dis[des];
}
int main()
{

	int n, m, src, des; 
	cin >> n >> m >> src >> des;
	assert(n > 0);
	vector< pair<int> > mp[N];
	for (int i = 0, u, v, w; i < m; i++) {
		cin >> u >> v >> w;
		mp[u].emplace_back(v, w);
	}	
	cout << spfa(src, des, mp, n) + spfa(des, src, mp, n) << endl;
	system("pause");
	return 0;
}
	
</int></int></bool></int></int></queue></vector></iostream>

发表于 2019-07-23 21:40:09 回复(0)

流浪打工人

Dijkstra's algorithm(迪杰斯特拉算法)，但是通过率只有百分之70，求解

#include<bits/stdc++.h>

using namespace std;
int arr[10001][10001];
int dis[10001];
bool visit[10001];
int path[10001];
void distra( int S,int N)
{
    memset(visit, 0, sizeof(visit));
    visit[S] = true;
    for (int i = 0; i < N; i++)
    {
        dis[i] = arr[S][i];
        path[i] = S;
    }
    int min, min_index;
    for (int i = 1; i < N; i++)
    {
        min = INT_MAX;
        for (int j = 0; j < N; j++)
        {
            if (visit[j] == false && dis[j] < min )
            {
                min = dis[j];
                min_index = j;
            }
        }
        visit[min_index] = true;
        for (int j = 0; j < N; j++)
        {
            if (visit[j] == false &&
                arr[min_index][j] != INT_MAX &&
                arr[min_index][j] + min < dis[j] )
            {

                dis[j] = arr[min_index][j] + min;
                path[j] = min_index;

            }
        }
    }
}
int main(void)
{
    int M, N, S, T;
    while (cin >> N >> M >> S >> T)
    {
        for (int i = 0; i < N+1; i++)
            for (int j = 0; j < N+1; j++)
                arr[i][j] = INT_MAX;//初始化临接矩阵

        int u, v, w;
        for (int i = 0; i < M; i++)
        {
            cin >> u >> v >> w;
            arr[u][v] = w;
        }
        distra(S,N+1);
        int a1 = dis[T];
        distra(T, N + 1);
        cout << a1 + dis[S] << endl;

    }

}

发表于 2018-05-29 11:07:23 回复(5)

岚の风

//短小精悍的代码~
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int n,m,s,t;
struct Node
{
    int t;
    int dis;
    Node(int t,int dis):t(t),dis(dis){}
    bool operator < (const Node& n)const
    {
        return dis>n.dis;
    }
};
vector<Node> V[10002];//vector模拟边表
bool hs[10002];//访问标记
int findPath(int s,int t)//dijkstra优先队列优化
{
    memset(hs,0,sizeof(hs));
    priority_queue<Node> Q;
    Node tmp(s,0);
    Q.push(tmp);
    while(!Q.empty())
    {
        tmp = Q.top();
        Q.pop();
        int src=tmp.t;
        int dis=tmp.dis;
        if(hs[src])//剪枝，弹出的节点已是最短距离，标记不再次进行搜索或放入队列
            continue;
        hs[src]=1;
        if(src==t)
            return dis;
        for(int i=0;i<V[src].size();++i)
        {
            int to = V[src][i].t;
            int todis=dis+V[src][i].dis;
            if(!hs[to])
            {
                Q.push(Node(to,todis));
            }
        }
    }
    return 10000000;//路径不可达
}
int main()
{
    cin>>n>>m>>s>>t;
    int a,b,c;
    while(m--)
    {
        cin>>a>>b>>c;
        V[a].push_back(Node(b,c));
    }
    int result = findPath(s,t);
    result+=findPath(t,s);
    cout<<result<<endl;
    return 0;
}

发表于 2018-06-04 09:56:03 回复(0)

I/.O

测试用例有问题

发表于 2020-07-17 21:57:54 回复(0)

听风雨201809112118346

https://blog.csdn.net/u010155337/article/details/88060550，解题思路

发表于 2019-04-04 11:21:50 回复(0)

胡家六少爷

Python 超时表示很忧伤啊。。。

发表于 2018-07-04 22:14:31 回复(0)

脚本学生

//贪婪策略，我怎么感觉是牛客网的测试数据出了问题？？？？？  
let reader=require('readline'); 
let r1=reader.createInterface({ input:process.stdin,output:process.stdout}); 
let limit=1000; 
let table=new Array(); 
r1.on('line',line=>{ 
     table.push(line.split(" ").map(x=>parseInt(x))) 
     if(table.length==1) 
         limit=table[0][0]; 
     if(table.length==limit+1) 
     { 
         console.log(work(table)); 
         r1.close(); 
     } 
}); 
function work(value) 
{ 
     let limit=value[0][1],sum=0; 
     value.shift(); 
     value.sort((x,y)=>{ 
     if(x[1]-x[0]>y[1]-y[0]) 
          return -1; 
     else if((x[1]-x[0]===y[1]-y[0])) 
          return 0; 
     else 
          return 1; 
 }); 
 for(let i=0;i<value.length;i++) 
 { 
     while(value[i][0]<=limit) 
    { 
         sum+=(value[i][1]-value[i][0]); 
         limit-=value[i][0]; 
     } 
     if(limit===0) 
        break; 
 } 
     return sum; }