这题是我期中测试的一题水题,然而英文题目太长了不想读...后面考完被同学提醒后20分钟切了(心塞)
切完看了波题解,发现貌似我的方法跟大家都不一样呢...
常规做法: (Floyd)
这个有三页的题解了,本蒟蒻在此不多讲
时间复杂度 (O(n^3))
我的解法: (queue+dijkstrra)
可以发现,如果一个点绕了一圈后跑回远点,那么他所跑的路就是一圈周长
用这个思路,我们暴力枚举每个点跑 (dijkstra) .每次绕了一圈回到原点的时候(肯定比原点要大),我们更新答案,不更新原点(本来也不需要更新)
问题来了, (dijkstra) 不会从自己一条边出发,再从对吗跑回自己呢?
我们可以观察到一个点:左边端点所连的边跟右边端点所连的边没有任何关系.基于此,不管我们在点 (i) 的哪一个端点,我们只要确认去的点 (j) 跟点 (i) 所连接的端点的位置.例如我们在他的左端点,我们只将右端点放入队列.反之依然.(记得不要在端点之间建边)
int to = 1;//假设他在右端点(1为右端点,0为左端点)
for (int k : adj[v][0]) if (k==qf) goto abcd;假设在左端点找到,那么就之间下一步(因为如果他在左端点,他要去的地方是右端点,to表示的不是他现在的地方,而是要去的地方)
to = 0;//如果搜遍左端点都没找到,那么证明他现在在右端点,要去左端点
abcd:;
if (dist[v][to]>dist[qf][qs]+len[v]){//裸的dijkstra
dist[v][to] = dist[qf][qs]+len[v];
if (!inq[v][to]){inq[v][to] = true;q.push(make_pair(v,to));}
}
最后的答案更新方法:(在 (dijkstra) 里面更新)
if (v==pos && to==curr) {
ans = min(ans,dist[qf][qs]+len[pos]);
}
完整代码:
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
#define pp pair<int,int>
#define f first
#define s second
int n;
int len[105],ans = 1e9;
int dist[105][2];
bool inq[105][2];
vector<int> adj[105][2];
void dfs(int pos,int curr){
queue<pp> q;
memset(dist,0x3f3f,sizeof(dist));
dist[pos][curr] = 0;
q.push(make_pair(pos,curr));//起点(记得将起点状态放进去
while(!q.empty()){
int qf = q.front().f,qs = q.front().s;q.pop();
inq[qf][qs] = false;
for (int v : adj[qf][qs]){
int to = 1;
for (int k : adj[v][0]) if (k==qf) goto abcd;
to = 0;
abcd:;//上面讲的转移方式
if (dist[v][to]>dist[qf][qs]+len[v]){
dist[v][to] = dist[qf][qs]+len[v];
if (!inq[v][to]){inq[v][to] = true;q.push(make_pair(v,to));}
}
if (v==pos && to==curr) {
ans = min(ans,dist[qf][qs]+len[pos]);
}//如果他现在要去原点,那么更新答案
}
}
}
int main(){
cin >> n;
for (int i=0;i<n;i++){
int a,b,c,d; cin >> a >> b >> c >> d;
len[a] = b;
for (int j=0;j<c;j++) {
int t; cin >> t;
adj[a][0].push_back(t);
}
for (int j=0;j<d;j++){
int t; cin >> t;
adj[a][1].push_back(t);
}//分开左右端点建边
}
for (int i=1;i<=n;i++) {dfs(i,0);dfs(i,1);}
cout << ans;
}
复杂度仍然是 (O(n^3))
为什么呢?其实就是一个小地方:在寻找左右端点的时候最坏情况会做n次.这个转移用数组可以优化成 (O(1)) .加两行代码后可以变成 (O(n^2)) 然而过了就懒得改了
接下来将那位Java大佬的思路了(已得到授权):
大佬的地址
其实区别也不大,就是将 (queue) 改成了 (priority) (queue) ,再加上一些小细节的区别
存图方法: 用 (hashset) 来代替数组,保证能在 (O(logn)) 的速度找到这个数
更新答案方式:他将每个点的距离改为 (inf) (包括原点),在原点出发时直接更新而不是取最小值.跑完之后只需要取原点的距离就是最终答案
求是否在端点上:
if(j==i) {//去左端点
if(!seg[i].hs2.contains(e.v))continue;//这个点不在右端点就不做
dist[i] = Math.min(dist[i], seg[i].l+e.w);}//看看自己能不能更新
if(seg[j].l+e.w < dist[j]) {
dist[j] = seg[j].l + e.w;
pq.add(new Status(e.v,j,dist[j]));
}//pq更新下一个数
}
完整代码:
import java.io.*;
import java.util.*;
public class Main {
private static StreamTokenizer st;
private static int nextInt()throws IOException{
st.nextToken();
return (int)st.nval;
}
public static void main(String args[]) throws IOException{
st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
int N = nextInt();
Segment[] seg = new Segment[N];
for(int i = 0; i < N; ++i) {
int s = nextInt()-1, l = nextInt(), n1 = nextInt(), n2 = nextInt();
seg[s] = new Segment(l);
for(int j = 0; j < n1; ++j)seg[s].hs1.add(nextInt()-1);
for(int j = 0; j < n2; ++j)seg[s].hs2.add(nextInt()-1);
}//记图
//bfs
PriorityQueue<Status> pq = new PriorityQueue<>();
int ans = Integer.MAX_VALUE;
for(int i = 0; i < N; ++i) {
//go from hs1 and back to hs2
int dist[] = new int[N];
Arrays.fill(dist, Integer.MAX_VALUE);
for(int j : seg[i].hs1) {
pq.add(new Status(i,j,seg[j].l));
dist[j] = seg[j].l;
}
while(!pq.isEmpty()) {
Status e = pq.poll();
if(e.w != dist[e.v])continue;
if(seg[e.v].hs1.contains(e.u)) {
//往右端点走的情况
for(int j : seg[e.v].hs2) {
if(j==i) {
if(!seg[i].hs2.contains(e.v))continue;
dist[i] = Math.min(dist[i], seg[i].l+e.w);
}
if(seg[j].l+e.w < dist[j]) {
dist[j] = seg[j].l + e.w;
pq.add(new Status(e.v,j,dist[j]));
}
}
}else {
//往左端点走的情况
for(int j : seg[e.v].hs1) {
if(j==i) {
if(!seg[i].hs2.contains(e.v))continue;
dist[i] = Math.min(dist[i], seg[i].l+e.w);
}
if(seg[j].l+e.w < dist[j]) {
dist[j] = seg[j].l + e.w;
pq.add(new Status(e.v,j,dist[j]));
}
}
}
}
ans = Math.min(ans, dist[i]);
}
PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
pw.println(ans);
pw.close();
}
private static class Segment{
int l;
HashSet<Integer> hs1, hs2;
public Segment(int l) {
this.l = l;
hs1 = new HashSet<>();
hs2 = new HashSet<>();
}
}
private static class Status implements Comparable<Status>{
int u, v, w;
public Status(int u, int v, int w) {
this.u = u;
this.v = v;
this.w = w;
}
@Override
public int compareTo(Status o) {
return w-o.w;
}
}
}
复杂度 (O(n^2log^2n)) 第一个 $log $在 (pq) ,第二个 (log) 在 (set).然而由于 (priority) (queue) (dijkstra) 的性质,在正常情况下跑不满这个时间,预估时间 (O(n^2)).
然而这位大佬用的java,于是在洛谷时间被虐的体无完肤