洛谷 P1629 邮递员送信（java实现）

P1629 邮递员送信

题目描述

有一个邮递员要送东西，邮局在节点 1。他总共要送 n-1样东西，其目的地分别是节点 2 到节点 n。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有 m条道路。这个邮递员每次只能带一样东西，并且运送每件物品过后必须返回邮局。求送完这 n-1样东西并且最终回到邮局最少需要的时间。

输入格式

第一行包括两个整数，n和 m，表示城市的节点数量和道路数量。

第二行到第 (m+1)行，每行三个整数，u,v,w表示从 u到 v有一条通过时间为 w的道路。

输出格式

输出仅一行，包含一个整数，为最少需要的时间。

输入输出样例

输入 #1

5 10
2 3 5
1 5 5
3 5 6
1 2 8
1 3 8
5 3 4
4 1 8
4 5 3
3 5 6
5 4 2

输出 #1

83

说明/提示

对于 30% 的数据，1≤n≤200。

对于 100% 的数据，1≤n≤10^{3，1≤*m*≤10}5，1≤u,v≤n，1≤w≤10^4，输入保证任意两点都能互相到达。

题解一

package p1629;import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
//	被卡数据了只能过60%
public class Main {static int N = 1010,M = 100010,INF = 0x3f3f3f3f;static int n,m;static int h[] = new int[N],e[] = new int[M],ne[] = new int[M],w[] = new int[M],idx = 0;static int dist[] = new int[N];static boolean st[] = new boolean[N];public static void add(int a,int b,int c) {e[idx] = b;ne[idx] = h[a];w[idx] = c;h[a] = idx++;}public static void spfa() {Queue<Integer> q = new LinkedList<>();Arrays.fill(dist, INF);Arrays.fill(st, false);q.add(1);st[1] = true;dist[1] = 0;while(!q.isEmpty()) {int t = q.poll();st[t] = false;for(int i = h[t];i!=-1;i=ne[i]) {int j = e[i];if(dist[j]>dist[t]+w[i]) {dist[j] = dist[t] + w[i];if(!st[j]) {q.add(j);st[j] = true;}}}}}public static void main(String[] args) throws Exception{BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));String str[] = bf.readLine().split(" ");n = Integer.parseInt(str[0]);m = Integer.parseInt(str[1]);Arrays.fill(h, -1);int mm = m;String s = "";while(m-->0) {String ss = bf.readLine();str = ss.split(" ");s+=ss+":";int a = Integer.parseInt(str[0]),b = Integer.parseInt(str[1]),c = Integer.parseInt(str[2]);add(a,b,c);}bf.close();int sum = 0;spfa();for(int i=1;i<=n;i++) {sum+= dist[i];}idx = 0;Arrays.fill(h, -1);str = s.split(":");for(int i=0;i<mm;i++) {//	建反图String ss[] = str[i].split(" ");int a = Integer.parseInt(ss[0]),b = Integer.parseInt(ss[1]),c = Integer.parseInt(ss[2]);add(b,a,c);}spfa();for(int i=1;i<=n;i++) {sum+= dist[i];}System.out.println(sum);}
}

题解二

package p1629;import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;
import java.util.PriorityQueue;public class Main2 {static int N = 1010,M = 100010,INF = 0x3f3f3f3f;static int n,m;static int h[] = new int[N],w[] = new int[M],e[] = new int[M],ne[] = new int[M],idx=0;static int dist[] = new int[N];static boolean st[] = new boolean[N];public static void add(int a,int b,int c) {e[idx] = b;w[idx] = c;ne[idx] = h[a];h[a] = idx++;}public static void dijkstra() {PriorityQueue<Pair> q = new PriorityQueue<>();Arrays.fill(dist, INF);Arrays.fill(st, false);q.add(new Pair(1,0));dist[1] = 0;while(!q.isEmpty()) {Pair p = q.poll();int t = p.x;if(st[t]) continue;st[t] = true;for(int i=h[t];i!=-1;i=ne[i]) {int j = e[i];if(dist[j] > dist[t]+ w[i]) {dist[j] = dist[t] + w[i];q.add(new Pair(j,dist[j]));}}}}public static void main(String[] args) throws IOException {Read read = new Read();n = read.nextInt();m = read.nextInt();Arrays.fill(h, -1);String str[] = new String[m];for(int i=0;i<m;i++) {int a = read.nextInt(),b = read.nextInt(),c = read.nextInt();str[i] = a+"-"+b+"-"+c;add(a,b,c);}dijkstra();int sum = 0;for(int i=1;i<=n;i++) {sum += dist[i];}Arrays.fill(h, -1);idx = 0;for(int i=0;i<m;i++) {String s[] = str[i].split("-");int a = Integer.parseInt(s[0]),b = Integer.parseInt(s[1]),c = Integer.parseInt(s[2]);add(b,a,c);}dijkstra();for(int i=1;i<=n;i++) {sum += dist[i];}System.out.println(sum);}
}class Read{StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));public int nextInt() throws IOException {st.nextToken();return (int)st.nval;}
}
class Pair implements Comparable<Pair>{int x,y;public Pair(int a,int b) {x=a;y=b;}@Overridepublic int compareTo(Pair o) {return this.y - o.y;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！