定义如下图所示的比赛地图:
S表示比赛起点,E表示比赛终点。实线表示陆路,虚线表示水路。兔子只能走陆路,乌龟既可以走陆路也可以走水路。每条路径的长度在图中给出。假定兔子和乌龟足够聪明,问谁先到达终点。
第1行输入v1,v2。v1是兔子的速度,v2是乌龟的速度(水路、陆路速度相同)。第2行输入n,m,点的编号是1~n,然后是m行,其中1是起点,n是终点(路径本身不限定方向)。下面m行4个数 a, b, d, c,表示a和b之间有一条边,且其长度为d,类型是c(0表示陆路,1表示水路)。最后一行是end,表示输入结束。输入保证1和n之间至少有一条路径联通。(1<n<=10000, 0<m<=1000000)。
输出-1,0,1中的一个数。-1表示乌龟获胜,1表示兔子获胜,0表示同时到达终点。
10 5 3 3 1 2 30 0 2 3 20 0 1 3 20 1 end
-1
通用Dijkstra求全路径点到点的距离代码,稍微修改就可以适用本题
/* Dijkstra算法求单源无向图最短路径 */ #include <bits/stdc++.h> using namespace std; struct node { int point, value; node(int a, int b) // 构造 { point = a; value = b; } // 重载<操作符 由小到大排序 bool operator<(const node &a) const { // 对小于运算符进行重载,如果两个值相等,那么继续判断point,如果不等,则返回false if (value == a.value) { return a.point < point; } else { return a.value < value; } } }; class Dijkstra{ public: Dijkstra(int count):n(count){ processE();//处理输入 result = vector<vector<int>>(count,vector<int>(count)); }; //求解无向图中所有点之前的距离 void solver(bool debug=true){ for(unsigned int i=1;i<=n;++i){ result.push_back(dijkstra(i)); if(debug){ for(int x:result.back()){ cout<<x<<' '; } cout<<endl; } } } //start是实际的标号,从1开始,在处理中数组从0开始 vector<int> dijkstra(int start) { vector<int> dis(n+1,INT_MAX); priority_queue<node> q;//每次求解需要的优先队列 dis[start] = 0; q.push(node(start, dis[start] )); while (!q.empty()) { node x = q.top(); q.pop(); for (int i = 0; i < e[x.point].size(); i++) { node y = e[x.point][i]; // 核心思想:更新估算距离,松弛 if (dis[y.point] > dis[x.point] + y.value) { dis[y.point] = dis[x.point] + y.value; q.push(node(y.point, dis[y.point])); } } } return vector<int>(dis.begin()+1,dis.end()); } void processE(){ //这个函数用来处理e[Ni]需要将start,end ,length添加到e[start]->(end,length)和e[end]->(start,length) //形如e[start].push_back(node(end[[2,1,1],[2,3,1],[3,4,1]], length)); int a, b, c, k; char s; getchar(); while(getchar() == '[') { scanf("%d%c%d%c%d%c%c", &a, &s, &b, &s, &c, &s, &s); e[a].push_back(node(b, c)); e[b].push_back(node(a,c)); } } private: vector<vector<int>> result;//最后的结果矩阵 const static int Ni = 101 ;//最大的边的集合 vector<node> e[Ni];//用起点表示的边的集合 int n ;//实际的边的个数 }; int main(){ Dijkstra(4).solver(); }
import java.util.*; public class Main { static class Graph { private Node start; private Node end; private final Map<Long, Node> map = new HashMap<>(); } static class Node { final long id; final Map<Way, Node> wayMap = new TreeMap<>(); Node(long id) { this.id = id; } } static class Way implements Comparable<Way> { long len; int type; Way(long len, int type) { this.len = len; this.type = type; } @Override public int compareTo(Way o) { return Long.compare(len, o.len); } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); long v1 = sc.nextLong(); long v2 = sc.nextLong(); long n = sc.nextInt(); long m = sc.nextInt(); Graph g = new Graph(); for (int i = 0; i < m; i++){ long src = sc.nextInt(); long tar = sc.nextInt(); long d = sc.nextLong(); int type = sc.nextInt(); Node s = g.map.get(src); if(s == null) { s = new Node(src); g.map.put(src, s); } Node t = g.map.get(tar); if(t == null) { t = new Node(tar); g.map.put(tar, t); } s.wayMap.put(new Way(d, type), t); if(src == 1) { g.start = s; } if(tar == 1) { g.start = t; } if(src == n) { g.end = s; } if(tar == n) { g.end = t; } } if(g.start == null || g.end == null) { System.out.println(0); } double t1 = bfs(g, v1, false); double t2 = bfs(g, v2, true); if(Math.abs(t1 - t2) < 0.001) { System.out.println(0); } else { System.out.println(t1 < t2 ? "1" : "-1"); } } private static double bfs(Graph g, long speed, boolean water) { Map<Long, Long> vis = new HashMap<>(); Queue<Node> queue = new LinkedList<>(); Queue<Long> wayQueue = new LinkedList<>(); queue.offer(g.start); wayQueue.offer(0L); vis.put(g.start.id, 0L); while (!queue.isEmpty()) { Node n = queue.poll(); long w = wayQueue.poll(); n.wayMap.forEach((way, nd) -> { if(!water && way.type == 1) { return; } Long before = vis.get(nd.id); if(before != null && w + way.len >= before) { return; } vis.put(nd.id, w + way.len); queue.offer(nd); wayQueue.offer(w + way.len); }); } Long ans = vis.get(g.end.id); if(ans == null) { ans = Long.MAX_VALUE; } return (double) ans / speed; } }Dijkstra算法,只不过数字范围有点坑,干脆全部用long
#include <cstdio> #include <vector> #include <queue> #include <climits> using namespace std; struct Edge{ int from, to, dist, type; }; struct HeapNode { int u; long d; bool operator<(const HeapNode& rhs) const { return d>=rhs.d; } }; vector<Edge> edges; // flag=true表示可走水路 int dijskra(vector<vector<int>>& G, int s, int t, bool flag) { int n = G.size()-1; vector<bool> visited(n+1, false); vector<long> d(n+1, INT_MAX); priority_queue<HeapNode> Q; d[s] = 0; Q.push((HeapNode){s,0}); while (!Q.empty()) { int u = Q.top().u; Q.pop(); if (u==t) break; if (visited[u]) continue; visited[u] = true; int num = G[u].size(); for (int i = 0; i < num; ++i) { Edge& e = edges[G[u][i]]; if (!flag && e.type==1) continue; if (d[u]+e.dist < d[e.to] && !visited[e.to]) { d[e.to] = d[u]+e.dist; Q.push((HeapNode){e.to, d[e.to]}); } } } return d[t]; } int main() { int n, m, v1, v2; scanf("%d%d%d%d", &v1,&v2,&n,&m); vector<vector<int>> G(n+1); for (int i = 0; i < m; ++i) { int from, to, dist, type; scanf("%d%d%d%d", &from, &to, &dist, &type); edges.push_back((Edge){from, to, dist, type}); G[from].push_back(edges.size()-1); edges.push_back((Edge){to, from, dist, type}); G[to].push_back(edges.size()-1); } double dist1 = dijskra(G,1,n,false); // 兔子的最短路径 double dist2 = dijskra(G,1,n,true); // 乌龟的最短路径 int result = 0; if (dist1/v1 < dist2/v2) result = 1; else if (dist1/v1 > dist2/v2) result = -1; printf("%d\n", result); return 0; }
import heapq import math # 看了B站灯神的BFS第三讲做的,用例通过90%,还有一个代码输入的地方报错,怀疑是测试用例有问题 class Solution(object): def main(self): while True: ins = input() if ins == 'end': break else: v1, v2 = map(int, ins.strip().split(' ')) n, m = map(int, input().strip().split(' ')) graph = {} for i in range(m): lst = list(map(int, input().strip().split(' '))) if lst[0] not in graph: graph[lst[0]] = {lst[1]: (lst[2], lst[3])} else: graph[lst[0]][lst[1]] = (lst[2], lst[3]) if lst[1] not in graph: graph[lst[1]] = {lst[0]: (lst[2], lst[3])} else: graph[lst[1]][lst[0]] = (lst[2], lst[3]) distance_g = self.dijkstra(graph, 1, False) distance_t = self.dijkstra(graph, 1, True) g = distance_g[n] / v2 t = distance_t[n] / v1 if g > t: print(1) elif g == t: print(0) else: print(-1) def dijkstra(self, graph, s, flag): pqueue = [] heapq.heappush(pqueue, (0, s)) seen = set() distance = self.inin_distance(graph, s) while pqueue: pair = heapq.heappop(pqueue) dist = pair[0] node = pair[1] seen.add(node) nodes = graph[node].keys() for w in nodes: if w not in seen: if flag and graph[node][w][1] == 1: continue if graph[node][w][0] + dist < distance[w]: heapq.heappush(pqueue, (graph[node][w][0] + dist, w)) distance[w] = graph[node][w][0] + dist return distance def inin_distance(self, graph, s): distance = {} for node in graph: if node != s: distance[node] = math.inf return distance Solution().main()
import java.util.*; public class Main{ public static void main(String[] args){ Main m = new Main(); m.input(); m.sovle(); if(m.time1 < m.time2) System.out.println("1"); else if(m.time1 > m.time2) System.out.println("-1"); else System.out.println("0"); } static class Node{ int id; public Node(int id){ this.id = id; } //从此节点出发到目标节点的路 LinkedList<Road> roads = new LinkedList<>(); } static class Road{ int target; long pathL; int type; public Road(int target,long pathL,int type){ this.target = target; this.pathL = pathL; this.type = type; } } int v1,v2; Map<Integer,Node> gragh = new HashMap<>(); int n,m; public void input(){ Scanner sc = new Scanner(System.in); v1 = sc.nextInt(); v2 = sc.nextInt(); n = sc.nextInt(); m = sc.nextInt(); //构建图 for(int i = 0;i < m;i++){ int s = sc.nextInt(); int t = sc.nextInt(); long l = sc.nextLong(); int type = sc.nextInt(); Node nodeS = gragh.get(s); if(nodeS == null){ nodeS = new Node(s); gragh.put(s,nodeS); } Node nodeT = gragh.get(t); if(nodeT == null){ nodeT = new Node(t); gragh.put(t,nodeT); } //将这条路添加到nodeS nodeS.roads.add(new Road(t,l,type)); } } public void sovle(){ //兔子 LinkedList<Node> stack = new LinkedList<>(); stack.add(gragh.get(1)); pathLong.put(1,0L); dijkstra(stack,false); time1 = pathLong.get(n)/(float)v1; //乌龟 stack.add(gragh.get(1)); pathLong.clear(); pathLong.put(1,0L); dijkstra(stack,true); time2 = pathLong.get(n)/(float)v2; } float time1,time2; //从1节点到达这个节点的路径长度 Map<Integer,Long> pathLong = new HashMap<>(); private void dijkstra(LinkedList<Node> stack,boolean water){ while (!stack.isEmpty()){ Node cur = stack.pop(); for(Road r : cur.roads){ //不能走水路,并且这条路是水路 if(!water && r.type == 1) continue; long curPathLong = pathLong.get(cur.id) + r.pathL; //路径目标节点已有值,并且当前路径的长度要大于目标已有路径的值 if(pathLong.get(r.target) != null && curPathLong >= pathLong.get(r.target)) continue; //设置目标路径长度 pathLong.put(r.target,curPathLong); //添加到栈尾 stack.add(gragh.get(r.target)); } } } }
80%C ++,没用longlong的原因,我感觉是
#include <iostream> #include <queue> #include <sstream> #include <vector> #include <cstring> #include <functional> using namespace std; const int N = 1e4 + 10; const int M = 1e6 + 10; int n, m; typedef pair<int, int> PII; int v1, v2; class D { public: void init() { //int h[N], e[M], ne[M], w[M], idx; memset(h, -1, sizeof h); memset(e, 0, sizeof e); memset(ne, 0, sizeof ne); memset(w, 0, sizeof w); //static int idx = 0; } void add(int a, int b, int c) { e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx++; } int djkstra(int n) { memset(dis, 0x3f, sizeof(dis)); memset(st, false, sizeof st); dis[1] = 0; priority_queue<PII, vector<PII>, greater<PII>> heap; heap.push({ 0, 1 }); while (heap.size()) { auto t = heap.top(); heap.pop(); int ver = t.second; int distance = t.first; if (st[ver]) continue; st[ver] = true; for (int i = h[ver]; i != -1; i = ne[i]) { int j = e[i]; if (dis[j] > distance + w[i]) { dis[j] = distance + w[i]; heap.push({ dis[j], j }); } } } return dis[n]; } private: int dis[N]; int h[N], e[M], ne[M], w[M], idx = 0; bool st[N]; }; int string_to_int(string s){ stringstream ss; ss << s; int foo; ss >> foo; return foo; } int main() { cin >> v1 >> v2; cin >> n >> m; string str; D d1; // 兔子 D d2; //鬼 d1.init(); d2.init(); while (cin >> str, str[0] != 'e') { int a = string_to_int(str); int b, c, d; scanf("%d%d%d", &b, &c, &d); if (d == 1) { d2.add(a, b, c); } else { d1.add(a, b, c); d2.add(a, b, c); } } int t1 = d1.djkstra(n); int t2 = d2.djkstra(n); //cout << t1 << " " << t2 << endl; if (t1*v2 < t2*v1 ) puts("1"); else if (t1*v2 == t2*v1) puts("0"); else puts("-1"); }
#include <bits/stdc++.h> #define int long long using namespace std; const int MAXN = 10010; const int INF = 0x7fffffff; const double exps = 1e-9; struct Edge{ int from, to, dist; Edge(int _from, int _to, int _dist):from(_from), to(_to), dist(_dist){} }; class Dijkstra{ public: struct node{ int d, u; node(int _d, int _u):d(_d), u(_u){} bool operator < (const node& rhs) const{ return d > rhs.d; } }; int n, m; vector <Edge> edges; vector <int> g[MAXN]; int dis[MAXN]; bool vis[MAXN]; Dijkstra(int _n, int _m):n(_n), m(_m){ for (int i = 0; i <= n; i++){ g[i].clear(); } edges.clear(); } void addEdge(int from, int to, int dist){ edges.push_back(Edge(from, to, dist)); edges.push_back(Edge(to, from, dist)); g[from].push_back((int)edges.size() - 2); g[to].push_back((int)edges.size() - 1); } int dijkstra(int s, int t){ priority_queue <node> q; for (int i = 0; i <= n; i++){ dis[i] = INF; } memset(vis, false, sizeof(vis)); dis[s] = 0; q.push(node(0, s)); while(!q.empty()){ node x = q.top(); q.pop(); int u = x.u; if(vis[u]){ continue; } vis[u] = true; for (int i = 0; i < g[u].size(); i++){ Edge& e = edges[g[u][i]]; if(dis[e.to] > dis[u] + e.dist){ dis[e.to] = dis[u] + e.dist; q.push(node(dis[e.to], e.to)); } } } return dis[t]; } }; int string_to_int(string s){ stringstream ss; ss << s; int foo; ss >> foo; return foo; } signed main(){ int v1, v2; int n, m; scanf("%lld %lld", &v1, &v2); scanf("%lld %lld", &n, &m); Dijkstra d1(n, m); Dijkstra d2(n, m); string s; int a, b, c, d; while(cin >> s){ if(s == "end"){ break; } a = string_to_int(s); scanf("%lld %lld %lld", &b, &c, &d); if(d == 0){ d1.addEdge(a, b, c); } d2.addEdge(a, b, c); } int f = d1.dijkstra(1, n) * v2; int e = d2.dijkstra(1, n) * v1; if(f > e) cout << "-1" << "\n"; else if(f < e) cout << "1" << '\n'; else cout << "0" << "\n"; return 0; }
# include<iostream> # include<vector> # include<utility> # define INFTY 1000000000 using namespace std; double Dijstra(vector<vector<double>>); double Dijstra_rabbit(vector<vector<double>>, vector<vector<int>>); int main(){ double v_rabbit, v_turtle; while(cin>>v_rabbit>>v_turtle){ int node_num, road_num; cin>>node_num>>road_num; vector<vector<double>> dist(node_num, vector<double>(node_num, -1)); vector<vector<int>> type(node_num, vector<int>(node_num, 0)); for(int i = 0; i < node_num; i++) dist[i][i] = 0; for(int i = 0; i < road_num; i++){ int a, b, d; double c; cin>>a>>b>>c>>d; dist[a - 1][b - 1] = c; dist[b - 1][a - 1] = c; type[a - 1][b - 1] = d; type[b - 1][a - 1] = d; } string endstr; cin>>endstr; //求最短路径 double d_turtle = Dijstra(dist); double d_rabbit = Dijstra_rabbit(dist, type); double time_turtle = d_turtle / v_turtle; double time_rabbit = d_rabbit / v_rabbit; if(time_turtle < time_rabbit) cout<< -1<<endl; else if(time_turtle > time_rabbit) cout<< 1<<endl; else cout<<0<<endl; } return 0; } double Dijstra(vector<vector<double>> dist){ //乌龟 int n = dist.size(); vector<bool> visit(n, false); vector<double> d(n, INFTY); d[0] = 0; while(true){ double mindist = INFTY; int u = 0; for(int i = 0; i < n; i++){ if(!visit[i] && d[i] < mindist){ u = i; mindist = d[i]; } } if(mindist == INFTY) break; visit[u] = true; for(int v = 0; v < n; v++){ if(!visit[v] && dist[u][v] != -1) d[v] = min(dist[u][v] + d[u], d[v]); } } return d[n - 1]; } double Dijstra_rabbit(vector<vector<double>> dist, vector<vector<int>> type){ int n = dist.size(); vector<bool> visit(n, false); vector<double> d(n, INFTY); d[0] = 0; while(true){ double mindist = INFTY; int u = 0; for(int i = 0; i < n; i++){ if(!visit[i] && d[i] < mindist){ u = i; mindist = d[i]; } } if(mindist == INFTY) break; visit[u] = true; for(int v = 0; v < n; v++){ if(!visit[v] && dist[u][v] != -1 && type[u][v] == 0) d[v] = min(dist[u][v] + d[u], d[v]); } } return d[n - 1]; }郁闷了,为啥提示段错误。。只能过70%,找不到出错的地方啊