白駿-139号重量制限

質問する

複数の島と重量制限のある橋がある場合
ある工場がある島から、別の工場がある島に移せるものの最大重量を求めます.

の意見を打診

ある工場がある島から、別の工場がある島を探索

時間の複雑さ

グラフィック問題の時間的複雑さは確定しにくいので,時間的複雑さを考慮したほうがよい.
島は最大10000個、橋は最大100000個
島はずっと1文字に並んでいて、工場は島の果てと果てにあり、
島の間に10の橋があるとしたら
島を渡るたびに10種類の状況があるからだ.
10^10000はとても大きいです
うん、だから私たちはただ振り返って、最大重量を求めることができないことを知っています.

タイムアウトのアイデア

だから私は
これまでのアクセス経路の最大重量は、通過する橋の最低重量制限であった.
ナビゲーション中に、島を通過するときに可能な最大重量を格納できます.
もう一つのルートで訪問した島にアクセスすると
以前に訪れた重量よりも重量が大きい場合にのみ,さらなる探索を行う.
より小さな重さは過ぎても正解にはなりません.
同じ大きさの重さがリピートナビ~!!!
うーん、これで処理するとタイムアウトしません(パチパチ)
私は心を込めて実現したが、タイムアウトした.
実装方法は次のとおりです.

//큐에 공장이 있는 한 섬(i1)을 넣어놓음
while (!q.empty()){
    int nownode = q.front().first;
    int nowweight = q.front().second;
    q.pop();

    //이미 다른 공장 섬(i2)에 도착했다면, 그 중량보다 큰 애들만 탐색하쟈
    if (nowweight <= check[i2]) {
        continue;
    }

    for (int i = 0; i < info[nownode].size(); i++) {
        int nextnode = info[nownode][i].first;
        int nextweight = info[nownode][i].second;
        //가능한 최대 중량은 지나온 다리들 중 제일 낮은 중량제한만큼
        nextweight = nowweight < nextweight ? nowweight : nextweight;

	//가봤자인 애들은 더 탐색 안 할랭
        if (nextweight <= check[i2] || check[nownode] == check[nextnode]) {
            continue;
        }
        
	//그전에 방문했던 중량보다 더 큰 중량으로 오는 경우에만 더 탐색
        if (check[nextnode] < nextweight) {
            check[nextnode] = nextweight;
            if (nextnode != i2) {
                q.push(make_pair(nextnode, nextweight));
            }
        }
    }
}

頭が完全に動く

うーん、これは素晴らしいアルゴリズムだと思いますが、タイムアウトしました.
何がこんなに長い間
彼は私にそばで最悪の状況を考えさせて、私は考えました.
う~ん、前に通ったルートよりよかったら行かせてください.
幸いなことに、私たちはまずできるだけ小さい子供たちを見つけました.
たとえ私がこのようにびっこを引いてifを処理しても、私は過去の状況があることを知っています.
(一つの島は最重で2過去、3過去、4過去...9過去...)
ああ～それは悲しいことだ
私はこのアルゴリズムを放棄することができないので、もう一度考えます.
あんな大きい子が先に行ったら、小さい子は通れないじゃないか.
(9を過ぎると2度3度4度…みんな探索終了に行けない!)
優先順位キューを使い、できるだけ最大重量の経路を探索します
そして~~~!~そう、へへへ
+私は彼にこの方法が何なのかと聞いたが、彼はbfs/dfsのような方法ではないと言った.プリンセスじゃないし.
優先順位キューが書かれたグラフを参照するだけです...彼は言った
++優先キューのpush時の時間複雑度はO(logn)
上記で説明した最悪の場合はO(logmN)くらいでしょうか?

もう少し時間を短縮してもらえますか?

Qでも上のアルゴリズムなら
もし私たちが初めて別の工場に着いたら、それは最大の価値でしょう.
A i 1から、そのままi 2まで返してみました

//새로운 섬을 탐색할 때 i2면 바로 출력하고 끝내~~
if (nextnode != i2) {
    q.push(make_pair(nextweight, nextnode));
}
else {
    cout << check[i2];
    return 0;
}

ああ、間違っています.
Q私が来たのは一番大きいと思いましたが、最後の探索の時
低い橋なので、最大重量が非常に小さくなります!
Aでは、i 2に到達したときに見られる最大可能重量がaであれば
Qに残っているメンバーの中ではAのメンバーだけが探索しているのでしょうか?
あ~aじゃない子の中でも答えかも~!~
もう二度と顔を出さないと思います.ほほほ

他の人のアルゴリズム

通常、2分ナビゲーションを使用して、重量として0～10000000の値を選択します.
BFSは工場から工場まで重量で通過できますか?
彼は方法で問題を解決した.
こちらの検索はO(logn)なのでCも早いです.
着いたら止まります.
私たちはすぐに問題を解決することができます.
この探索も心の中に置いておきましょう.

コード#コード#

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

int n, m, i1, i2;
int a, b, c;

int check[10005];
vector<pair<int, int>> info[10005];
priority_queue<pair<int, int>> q;
pair<int, int> tempq;

int main() {
	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		info[a].push_back(make_pair(c, b));
		info[b].push_back(make_pair(c, a));
	}

	cin >> i1 >> i2;

	check[i1] = 1000000005;
	q.push(make_pair(1000000005, i1));

	while (!q.empty())	{
		int nowweight = q.top().first;
		int nownode = q.top().second;
		q.pop();

		if (nowweight <= check[i2]) {
			continue;
		}

		for (int i = 0; i < info[nownode].size(); i++) {
			int nextweight = info[nownode][i].first;
			int nextnode = info[nownode][i].second;
			nextweight = nowweight < nextweight ? nowweight : nextweight;

			if (nextweight <= check[i2] || check[nownode] == check[nextnode]) {
				continue;
			}

			if (check[nextnode] < nextweight) {
				check[nextnode] = nextweight;
				if (nextnode != i2) {
					q.push(make_pair(nextweight, nextnode));
				}
			}
		}
	}

	cout << check[i2];

	return 0;
}