首页 > 试题广场 >

过年回家

[编程题]过年回家

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

NowCoder今年买了一辆新车，他决定自己开车回家过年。回家过程中要经过n个大小收费站，每个收费站的费用不同，你能帮他计算一下最少需要给多少过路费吗？

输入描述:

输入包含多组数据，每组数据第一行包含两个正整数m（1≤m≤500）和n（1≤n≤30），其中n表示有n个收费站，编号依次为1、2、…、n。出发地的编号为0，终点的编号为n，即需要从0到n。

紧接着m行，每行包含三个整数f、t、c，（0≤f, t≤n; 1≤c≤10），分别表示从编号为f的地方开到t，需要交c元的过路费。

输出描述:

对应每组数据，请输出至少需要交多少过路费。

示例1

输入

输出

算法知识视频讲解

Cavs

单源最短路径，dijkstra算法。
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<functional>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <exception>
#include <iomanip>
#include <memory>
#include <sstream>
#include <list>

using namespace std;

#define INF 10000

int main(int argc, char** argv)
{
	//freopen("in.txt", "r", stdin);
	int m,n;
	while (cin >> m >> n)
	{
		vector<vector<int>> cost(n + 1, vector<int>(n + 1, INF));
		int f, t, c;
		for (int i = 0; i < m; ++i)
		{
			cin >> f >> t >> c;
			cost[f][t] = c;
		}
		vector<int> minDis(n + 1, INF);
		vector<bool> visited(n + 1, false);
		minDis[0] = 0;
		while (true)
		{
			int next = -1;
			for (int i = 0; i <= n; ++i)
			{
				if (!visited[i] && (next == -1 || minDis[i] < minDis[next])) next = i;
			}

			if (next == -1) break;

			visited[next] = true;

			for (int i = 0; i <= n; ++i)
				minDis[i] = min(minDis[i], minDis[next] + cost[next][i]);
		}

		cout << minDis[n] << endl;
	}

	return 0;
}

发表于 2017-07-11 14:24:28 回复(0)

甫艾蒽廷

package test;
import java.util.Scanner;
public class TarStation {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while (in.hasNext()) {
			int m = in.nextInt();
			int n = in.nextInt();
			// 最短路径
			int dist[] = new int[n + 1];
			// 前一个顶点号
			int path[] = new int[n + 1];
			// 顶点是否被确定了
			boolean S[] = new boolean[n + 1];
			// 初始化邻接矩阵
			int[][] Edge = new int[n + 1][n + 1];
			for (int i = 0; i < n + 1; i++) {
				for (int j = 0; j < n + 1; j++) {
					Edge[i][j] = Integer.MAX_VALUE;
				}
			}
			// 输入邻接矩阵
			for (int i = 0; i < m; i++) {
				Edge[in.nextInt()][in.nextInt()] = in.nextInt();
			}
			Dijkstr(Edge, dist, path, S, m, n);
		}
	}
	private static void Dijkstr(int[][] edge, int[] dist, int[] path, boolean[] s, int m, int n) {
		for (int i = 0; i < n + 1; i++) {
			dist[i] = edge[0][i];
			if (i != 0 && dist[i] < Integer.MAX_VALUE)
				path[i] = 0;
			else
				path[i] = -1;
		}
		// 开始对对一个站进行操作
		s[0] = true;
		dist[0] = 0;
		// 从顶点v确定n条路径
		for (int i = 0; i < n; i++) {
			int min = Integer.MAX_VALUE, u = 0;
			// 选择当前不在S中具有最短路径的顶点u
			for (int j = 0; j < n + 1; j++) {
				if (!s[j] && dist[j] < min) {
					u = j;
					min = dist[j];
				}
			}
			// 表示u已经在最短路径上
			s[u] = true;
			for (int k = 0; k < n + 1; k++) {
				if (!s[k] && edge[u][k] < Integer.MAX_VALUE && dist[u] + edge[u][k] < dist[k]) {
					dist[k] = dist[u] + edge[u][k];
					path[k] = u;
				}
			}
		}
		System.out.println(dist[n] + "");
	}
}

发表于 2016-11-06 10:38:57 回复(1)

H掠影

floyd算法：

#include<iostream>

using namespace std;

int soudesmon[500][3];

int map[31][31];

int main()

{

int m,n;

while(cin>>m>>n)

{

for(int i=0;i<m;i++)

{

cin>>soudesmon[i][0];

cin>>soudesmon[i][1];

cin>>soudesmon[i][2];

}

int inf=999999;

for(int i=0;i<=n;i++)

{

for(int j=0;j<=n;j++)

{

if(j==i)

{

map[i][j]=0;

}

if(j!=i)

{

map[i][j]=inf;

}

for(int i=0;i<m;i++)

{

map[soudesmon[i][0]][soudesmon[i][1]]=soudesmon[i][2];

}

for(int k=0;k<=n;k++)

{

for(int i=0;i<=n;i++)

{

for(int j=0;j<=n;j++)

{

if(map[i][j]>map[i][k]+map[k][j])

{

map[i][j]=map[i][k]+map[k][j];

}

cout<<map[0][n]<<endl;

}

return 0;

}

发表于 2017-03-28 17:56:58 回复(0)

C/C++

lishiji

// write your code here cpp

//dijkstra算法，网上很多

#include <iostream>

#include <vector>

using namespace std;

int main(){

int m,n;

while(cin>>m>>n){

int from,to,cost;

vector<vector<int>> distance(n+1,vector<int>(n+1,1000));

for(int i=0;i<m;i++){

cin>>from>>to>>cost;

distance[from][to] = cost;

}

vector<int> nearest(n+1,1000);

for(int i=1;i<n+1;i++)

nearest[i] = distance[0][i];

vector<bool> in_sec(n+1,false);

in_sec[0]=true;

for(int i=1;i<n+1;i++){

int next=0;

int min = 1000;

for(int j=1;j<n+1;j++){

if(min>nearest[j]&&!in_sec[j])

{

min=nearest[j];

next = j;

}

if(next ==0)

break;//没有通路，

else

{

in_sec[next] = true;

for(int i=0;i<n+1;i++)

{

if(nearest[i]>nearest[next] + distance[next][i])

nearest[i] =nearest[next] + distance[next][i];

}

cout<<nearest[n]<<endl;

}

return 0;

}

发表于 2016-09-28 13:37:47 回复(0)

revivedSuN

#include <cstdio>
#include <algorithm>
using namespace std;
int main()
{ 
    int stations[31][31];
	int m,n,f,t,c;
	const int INF = 0x7fffffff;
	while(scanf("%d%d",&m,&n) != EOF){
		for(int i = 0; i <= n; i++){
			for(int j = 0; j <= n; j++) stations[i][j] = INF;
		}
		for(int i = 0; i < m; i++){
			scanf("%d%d%d",&f,&t,&c);
			stations[f][t] = c;
		}
		for(int k = 1; k <= n; k++){
			for(int i = 0; i <= n; i++){
				for(int j = 0; j <= n; j++){			
					if(k != i && k != j && i != j && stations[i][k] != INF && stations[k][j] != INF){
							stations[i][j] = min(stations[i][j],stations[i][k]+stations[k][j]);
					}
				}
			}
		}
		printf("%d\n",stations[0][n]);
	}
	return 0;
}

练练floyd

编辑于 2016-02-11 14:40:11 回复(0)

L0L

#include<iostream>
#include<vector>
#include<map>
using namespace std;
int main() {
	int m,n;
	int a,b,c;
	while(cin>>m>>n) {
		vector<vector<int> > mp(n+1,vector<int>(n+1));
		for(int i=0; i<n+1; i++) {//初始化所有距离 
			for(int j=0; j<n+1; j++) {
				if(i==j)	mp[i][j]=0;
				else   mp[i][j]=1<<12;
			}
		}
		while(m-->0) {
			cin>>a>>b>>c;
			mp[a][b]=c;//接受输入 
		}
		vector<int> dis(mp[0]);//结点0到其他点的距离 
		vector<bool> sp(n+1,false);//标记最短路径点集 
		for(int i=0;i<n+1;i++){
			int MIN=1<<12;
			int u;
			for(int j=0;j<n+1;j++){//扩展新的结点，即满足，到该节点的路径是剩余结点中最短的 
				if(!sp[j]&&dis[j]<MIN){
					u=j;
					MIN=dis[j];
				}
			}
			sp[u]=true;
			for(int k=0;k<n+1;k++){
				dis[k]=min(dis[k],dis[u]+mp[u][k]);
			}
		}
		cout<<dis[n]<<endl;
	}
	return 0;
}

发表于 2015-10-19 17:18:08 回复(0)

牛客210325号

package com.yzh.hehe;

import java.util.ArrayList; 
import java.util.List;
import java.util.Scanner;

//用题目上的提供的输入数据测试没有问题，但在用scanner 接收输入时会出格式上的错误（Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException），哪位大神指点指点
public class LeatestCarFee {

    public static void main(String[] args) { 
        String string="8 4";
        int m =Integer.valueOf(string.split("\\s+")[0]);
        int n =Integer.valueOf(string.split("\\s+")[1]);
        List<FeeLine>[] arr = new List[n]; 
        for (int i = 0; i < arr.length; i++) {
            arr[i]=new ArrayList<FeeLine>();
        }
        String[] tempArr={"0 1 10",
                "0 2 5",
                "1 2 2",
                "1 3 1",
                "2 1 3",
                "2 3 9",
                "2 4 2",
        "3 4 4"};
        for (int i = 0; i < m; i++) { 
            string=tempArr[i];
            String[] sArr = string.split("\\s+");
            makeGraph(arr, sArr);
        }
        System.out.println(leatestCarFee(arr));
        //以int类型接收输入格式错误（Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException）
//        Scanner scanner=new  Scanner(System.in); 
//        while (scanner.hasNext()) {   
//            int m =scanner.nextInt();
//            int n =scanner.nextInt(); 
//            List<FeeLine>[] arr = new List[n]; 
//            for (int i = 0; i < arr.length; i++) {
//                arr[i]=new ArrayList<FeeLine>();
//            } 
//            for (int i = 0; i < m; i++) { 
//                String[] sArr =  new String[3];
//                sArr[0]=String.valueOf(scanner.nextInt());
//                sArr[1]=String.valueOf(scanner.nextInt());
//                sArr[2]=String.valueOf(scanner.nextInt());
//                        
//                makeGraph(arr, sArr);
//            }  
//            System.out.println(leatestCarFee(arr));
//        }
//        scanner.close();
        //以字符串接收输入格式错误（Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException）
//        Scanner scanner=new  Scanner(System.in); 
//        while (scanner.hasNext()) {  
//            String string=scanner.nextLine(); 
//            int m =Integer.valueOf(string.split("\\s+")[0]);
//            int n =Integer.valueOf(string.split("\\s+")[1]);
//            List<FeeLine>[] arr = new List[n]; 
//            for (int i = 0; i < arr.length; i++) {
//                arr[i]=new ArrayList<FeeLine>();
//            } 
//            for (int i = 0; i < m; i++) {
//                string=scanner.nextLine();  
//                String[] sArr = string.split("\\s+");
//                makeGraph(arr, sArr);
//            }  
//            System.out.println(leatestCarFee(arr));
//        }
//        scanner.close();
    }

    private static int  leatestCarFee(List<FeeLine>[]  arr) {
        int[] costArr = new  int[arr.length+1];//记录起点到各点的最小值
        //索引0位置的值设为0（初始值）
        for (int i = 1; i < costArr.length; i++) {
            costArr[i]=Integer.MAX_VALUE;
        }
        int[] findArr=new int[arr.length+1];//是否被找到值得点
        int aim = 0; 
        while (aim!=arr.length) {
            findArr[aim]=1;
            aim=getLeatest(costArr, aim, arr,findArr); 
        }
        return costArr[aim];

    }

    //首先找到离起点值最小（v）的点（m），点m与起点的最小值即为v,再把v与点m的邻接点（n...）的值相加和起点到这些点（n...）的值作比较更新
    //重复以上步骤找出所求点到起点的最小值
    private static int getLeatest(int[] costArr, int point, List<FeeLine>[] arr,int[] findArr) {
         int size=arr[point].size();
         int pFee=costArr[point]; 
         for (int i = 0; i < size; i++) {
             FeeLine feeLine=arr[point].get(i);
            if (feeLine.fee+pFee<costArr[feeLine.point]) {
                costArr[feeLine.point]=feeLine.fee+pFee; 
            }
        }
         FeeLine rec=new FeeLine(Integer.MAX_VALUE, Integer.MAX_VALUE);
         for (int i = 1; i < costArr.length; i++) {
            if (costArr[i]<rec.fee&&findArr[i]!=1) {
                rec.fee=costArr[i];
                rec.point=i; 
            }
        }
         return rec.point; 
    }



    private static void makeGraph(List<FeeLine>[] arr,String[] sArr ) {
        FeeLine feeLine=new FeeLine(Integer.valueOf(sArr[1]), Integer.valueOf(sArr[2]));
        arr[Integer.valueOf(sArr[0])].add(feeLine);
    }



}




class FeeLine {
    int point;
    int fee;
    FeeLine(int point,int fee){
        this.point=point;
        this.fee=fee;
    }
}

发表于 2018-11-01 18:02:30 回复(0)

月晕潆洄

典型最短路问题...
我就想问问有没有人跟我一样没有看清是多组数据输入的，查了半天错..无***说

发表于 2017-06-16 23:12:03 回复(0)

sidian

//回溯法
#include<iostream>

using namespace std;
#define Max 1024

int edge[Max][Max];
int VerNum;
int EdgeNum;
int Current[Max];
int Bestcost;
int Currentcost;

void swap(int& a, int& b){
    int temp;
    temp = a;
    a = b;
    b = temp;
}

void Function(int m)
{	    
    for(int i = m; i<VerNum+1; i++){
     	swap(Current[m],Current[i]);
        if(edge[Current[m-1]][Current[m]]+Currentcost < Bestcost && edge[Current[m-1]][Current[m]]!=0)
        {
            if(Current[m]==VerNum){
                Bestcost = edge[Current[m-1]][Current[m]]+Currentcost;
            }
            else{
            	Currentcost += edge[Current[m-1]][Current[m]];
            	Function(m+1);
            	Currentcost -= edge[Current[m-1]][Current[m]];
            }
        }
        swap(Current[m],Current[i]);
    }
}

int main(){
    int Num =0;
    while(Num < 24)
    {
        Num++;
    	Bestcost = 10000;
    	Currentcost = 0;
    
    	cin>>EdgeNum>>VerNum;
    
    	for(int i=0; i<VerNum+1; i++)
    	{
     		for(int j=0; j<VerNum+1; j++)
        	{
           	edge[i][j]=0; 
        	}
    	}
    
    	int m,n;
    	for(int i=0; i<EdgeNum; i++)
    	{
        	int start,end,value;
        	cin >> start >> end >> value;
    		for(m=0;m!=start;m++);
        	for(n=0;n!=end;n++);
        	edge[m][n]=value;
    	}
    
    	for(int i=0; i<VerNum+1; i++){
        	Current[i] = i;
    	}
   
   	if(VerNum > 1){
    		Function(1);
    	}
    	else if(VerNum == 1){
        	Bestcost = edge[0][1];
    	}
   
    	cout << Bestcost << endl;
    }
}

发表于 2017-04-17 11:31:31 回复(0)

晓宇大美女~

请问各位大神，我的代码错在哪里了？为什么显示运行错误。说是数组越界，但是我检查了好几遍，数组没有越界啊o(╯□╰)o

import java.util.Scanner;

public class Main {
	private static final int MAX = 99999;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			int m = sc.nextInt();
			int n = sc.nextInt();
			int[][] data = new int[n+1][n+1];
   
			for (int i = 0; i < n + 1; i++) {
				for (int j = 0; j < n + 1; j++) {
					data[i][j] = MAX;
				}
			}
			
			for (int i = 0; i < m; i++) {
				int f = sc.nextInt();
				int t = sc.nextInt();
				int b = sc.nextInt();
				data[f][t] = b;
			}
			System.out.println(dija(data));
		}
	}

	public static int dija(int[][] map) {
		int n = map.length;
		// s中存放的是已经求得最短路径的点
		boolean[] s = new boolean[n];
		// 存放着源点到所有其他点的最短路径
		int[] d = new int[n];
		//int[] path = new int[n];

		for (int i = 0; i < n; i++) {
			s[i] = false;
			d[i] = map[0][i];
		}
		s[0] = true;
		d[0] = 0;
		for (int i = 1; i < n; i++) {
			int k = choose(d, s);
			s[k] = true; 
			for (int w = 0; w < n; w++) {
				if (!s[w] && d[k] + map[k][w] < d[w]) {
					d[w] = d[k] + map[k][w];
					//path[w] = k;
				}
			}
		}

		return d[n-1];
	}

	public static int choose(int[] d, boolean[] s) {
		int n = d.length;
		int min = MAX;
		int minPos = -1;
		for (int i = 0; i < n; i++) {
			if (d[i] < min && !s[i]) {
				min = d[i];
				minPos = i;
			}
		}
		return minPos;
	}
}

编辑于 2016-06-25 20:34:19 回复(0)

doodle777

Dijkstra算法求单源最短路径

#include <iostream>
#include <fstream>
#include <climits>
#include <algorithm>
#include <vector>
using namespace std;

int dijkstra(vector<vector<unsigned int> > & map)
{
	int n = map.size() - 1;
	vector<unsigned int> dist(map[0]);
	vector<int> final(n + 1, 0);

	//开始主循环 每次求得0到某个顶点select的最短路径 并加select到集合S中
	for (int i = 1; i <= n; ++i)
	{
		int select;
		int min = INT_MAX;
		for (int j = 0; j <= n; ++j)
		{
			if (!final[j])						//如果j顶点在V-S中
			{
				//选出当前V-S中与S有关联边 且权值最小的顶点
				if (dist[j] < min) { select = j; min = dist[j]; }
			}
		}
		final[select] = 1;						//选出该点后加入到合集S中
		for (int j = 0; j <= n; ++j)			//更新当前最短路径和距离
			if (!final[j] && (min + map[select][j]<dist[j]))
				dist[j] = min + map[select][j];
	}

	return dist[n];
}

int main() 
{
	int m, n;
	while (cin >> m >> n) 
	{
		vector<vector<unsigned int> > map(n + 1, vector<unsigned int>(n + 1));
		for (int i = 0; i <= n; i++)
		{
			for (int j = 0; j <= n; j++) 
			{
				if (i == j) map[i][j] = 0;
				else map[i][j] = INT_MAX;
			}
		}
		for (int i = 0; i < m; ++i)
		{
			int a, b, c;
			cin >> a >> b >> c;
			map[a][b] = c;
		}

		cout << dijkstra(map) << endl;
	}
	return 0;
}

发表于 2015-12-15 22:27:46 回复(0)

xiaoehaier

// write your code here cpp

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

#define min(a,b) ( ((a)>(b)) ? (b):(a) )

int weight[31], data[31][31];
bool undone[31];

int main()
{
    int m, n, f, t, c;
    while(~scanf("%d%d", &m, &n)){
        //initial
        memset(weight+1, 0x7f, sizeof(int)*30);
        memset(undone, true, sizeof(undone));
        memset(data, 0, sizeof(data));

        while(m--){
            scanf("%d%d%d", &f, &t, &c);
            data[f][t] = c;
        }
        
        //dijkstra
        int new_done = 0, least = -1;
        while(undone[n]){
            //update node linked with new_done
            //found least of all undone
            for(int i=1; i<=n; ++i){
                if(undone[i]){
                	if(least == -1) 
                        least = i;

                	if(data[new_done][i])
                        weight[i] = min(weight[i], weight[new_done]+data[new_done][i]);
                    
                	if(weight[least] > weight[i])
                        least = i;
            	}
            }
     
            undone[least] = false;
            new_done = least;
            least = -1;
        }
        printf("%d\n", weight[n]);
        
    }
    
    return 0;
}

发表于 2015-09-10 14:59:37 回复(0)