P1224 I Wanna Go Home - 题解

登录注册上岸

以下题解仅供学习参考使用。

抄袭、复制题解，以达到刷AC率/AC数量或其他目的的行为，在N诺是严格禁止的。

N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。

2024年6月25日 16:06

I Wanna Go Home 题解：无需多言

P1224

回复 0 | 赞 0 | 浏览 344

//#include <bits/stdc++.h> #include <iostream> #include <unordered_map> #include <queue> #define maxn 605 #define for_(i,a,b) \ for (int i = (a); i < (b); i++) #define INF 0x3f3f3f3f using namespace std; int n,m; u...

2022年7月5日 13:05

先利用Dijkstra或SPFA分别求出求出城市1和城市2到其阵营中其

P1224

回复 0 | 赞 2 | 浏览 5.5k

首先，查看答案里的大多数AC代码和几篇题解的思路是有问题的，我也是看了好久才发现这个思路是有问题的，比如数据： 3 3 1 2 100 1 3 40 2 3 50 1 2 2 路线应该是1->3->2，花费的最少时间为90，而他们那种方法的路线是直接1->2，花费了100的时间，显然是不正确的，但是也AC了，不过现在数据已加强，应该是通过不了了。那么我们现在利用其他思路来解决一下，有两种办法。在此之前，先分析一下题目的意思：目标是从城市1走到城市2，城市1和2周围是有很多城市的，给你每个城市之间的距离，且这些城市隶属两个阵营...

2021年1月26日 15:24

一点点变形

P1224

回复 7 | 赞 0 | 浏览 8.9k

#include<iostream> #include<string> #include<string.h> #include<vector> #include<stdio.h> #include <queue> #include<algorithm> using namespace std; const int maxn=105; struct Edge { int u; int v; int dis; Edge(int a,int b,int c):u(a)...

2022年7月5日 10:15

这道题的几个坑要注意一下

P1224

回复 0 | 赞 1 | 浏览 5.4k

首先是题意：因为是英文题，有同学题意没理解清楚。求的1到2的最短路，图是双向边，但是有阵营限制，只能跨一次阵营。然后有可能有重边，所以出现重边取值最小的，如果从1走不到2输出-1。还有一个关键点是，题目中说了默认初始时，城市1在阵营1，城市2在阵营2。所以只需要建图的时候处理一下就是一个很简单的最短路问题，不管是Dijkstra还是SPFA或者Floyd都可以做。我们只需要在建图的时候把跨阵营的双向边变成从阵营1到阵营2的单向边就可以了。因为只能跨阵营一次，所以不可能出现从阵营2到阵营1的答案的路线。

2021年4月23日 22:36

判断条件修改

P1224

回复 2 | 赞 1 | 浏览 9.0k

#include <iostream> #include <string> #include <algorithm> #include <vector> #include <cstring> #include <queue> #include <cmath> #define inf 0x3f3f3f3f #define MOD 100000 using namespace std; const int maxn = 600+6; struct Edge{ int...

2020年3月27日 21:58

很多人做不出来估计是没弄明白题目规则

P1224

回复 0 | 赞 1 | 浏览 9.3k

我来重新解释一下规则： 1. 城市分为两个阵营，阵营1和阵营2 ，每组输入的最后一行，是说明对应的每个城市所属的阵营，如 1 2 2 2 1 表示城市1，5 属于阵营1，城市2，3，4属于阵营2。 2. 两头的城市是不同阵营的道路，只允许走一次，即只能跨阵营一次，继续用上例说明： 1->3 走过之后，3->5不可以再走了，因为 1->3这条路已经用掉了跨阵营的唯一一次机会，那么剩下的路只能走 3->4->2了 3. 每组输入都是让输出从城市1 到城市2的花费，即求城市1到各城市的距离，输出数组中第二个元素。 ...

题目I Wanna Go Home

题解数量6

热门题解

1 先利用Dijkstra或SPFA分别求出求出城市1和城市2到其阵营中其它城市的最短路径，然后对阵营间存在的路径 i 到 j ，求dist(0, i)+D(i, j)+dist(1, j)的最小值

2 判断条件修改

3 很多人做不出来估计是没弄明白题目规则

4 这道题的几个坑要注意一下

5 I Wanna Go Home 题解：无需多言

6 一点点变形