BOJ 5719-ほぼ最短パス

23533 ワード
boj テキストリンク
タイムアウトメモリ制限正解正解の送信正解正解正解正解率毎秒256 MB 11956148493621.389%

質問する


現在、多くの車にGPSナビゲーション設備が搭載されています.ナビゲーションは、ユーザーが入力した開始点と到達点の間の最短パスを検索します.しかし、交通状況を考慮せずに最短経路を検索すると、深刻な渋滞を経験します.
尚根は自分でしか使えないナビを作っています.このナビゲーションでは絶対に最短パスは見つかりません.常に最短のパスを見つけることができます.
ほとんど最短経路とは、最短経路に含まれない道路のみからなる経路の中で最も短い経路を指す.
例えば、道路地図を考えてみると以下のようになります.円は場所を表し、線は一方向道路を表す.始点をS、終点をDとする.太い線は最短パスを表します.(下図中に最短経路が2本あります)ほぼ最短経路は破線で表される経路です.このパスは、最短パスに最短パスに含まれないパスです.ほとんどの最短パスに複数のパスが存在する可能性があります.例えば、下図に示す長さ3の道路長が1の場合、ほぼ最短経路は2本となる.また、最短経路がほとんどない場合もあります.

入力


入力は、複数のテスト・インスタンスから構成されます.各試験例の第1行は、地点数N(2≦N≦500)および道路数M(1≦M≦10⁴)を与える.場所番号は0からN-1までです.2行目は、開始点Sおよび到達点Dを与える.(S≠D;0≦S,D入力した最後の行には2つのゼロが表示されます.

しゅつりょく


各テストケースについて、最短パスの長さをほとんど出力します.最短パスがほとんどない場合は、-1が出力されます.

に近づく


これは多企業の応用問題に基づいている.
最初は複数の曲線でDまでの距離を求めて、前のノード(複数)を保存します.
DFSで巡回し、これらのEdgeを削除してからエストラに伝えます.
Nは500であるため,ノードを削除しやすい隣接行列で解くことを開始する.
しかし,いくつのテストケースがあるか分からないため,TLEが出現した.
そこで,Mapベースの隣接リストを用いたが,TLEが出現した.
DFSを用いてノードを削除する過程で重複処理は行われなかった.
メモのフォーマットはずっと重要です.

に答える


複数のカーブを最初に回転させると、beforeベクトルが作成され、以前のノードが格納されます.
また,DFSを用いて削除する過程で反復器を削除することで,重複アクセスが阻止される.
この後Sでもう一度回ります
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };

const int INF = 987654321;
int N, M, S, D, arr[500], u, v, w;
vector<int> before[500];
map<int, int> dist[500];

void DFS(int node)
{
	auto iter = before[node].begin();
	while(!before[node].empty())
	{
		dist[*iter][node] = -1;
		DFS(*iter);
		iter = before[node].erase(iter);
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	while (true)
	{
		CIN2(N, M);
		if (!N) break;
		CIN2(S, D);
		FUP(i, 0, N - 1)
		{
			dist[i].clear();
			arr[i] = INF;
			before[i].clear();
		}
		while (M--)
		{
			CIN3(u, v, w);
			dist[u][v] = w;
		}
		priority_queue<pair<int, int>> pq; // {거리, 노드}
		arr[S] = 0;
		pq.push({ 0, S });
		while (!pq.empty())
		{
			int node = pq.top().second;
			int d = -pq.top().first;
			pq.pop();
			if (node == D) break;
			for(auto p : dist[node])
			{
				int nd = p.second + d;
				if (nd > arr[p.first]) continue;
				else if (nd == arr[p.first]) before[p.first].push_back(node);
				else
				{
					before[p.first].clear();
					before[p.first].push_back(node);
					arr[p.first] = nd;
					pq.push({ -nd, p.first });
				}
			}
		}
		while (!pq.empty()) { pq.pop(); }
		DFS(D);

		FUP(i, 0, N - 1) arr[i] = INF;
		arr[S] = 0;
		pq.push({ 0, S });
		while (!pq.empty())
		{
			int node = pq.top().second;
			int d = -pq.top().first;
			pq.pop();
			if (node == D) break;
			for (auto p : dist[node])
			{
				if (p.second == -1 || p.second + d >= arr[p.first]) continue;
				arr[p.first] = d + p.second;
				pq.push({ -arr[p.first], p.first });
			}
		}
		arr[D] == INF ? COUT(-1) : COUT(arr[D]);
		ENDL;
	}

	return 0;
}
自動検出漢字GB 18030符号化とUTF-8符号化
第4週コード状態/DOM