読者です 読者をやめる 読者になる 読者になる

AOJ 0117 A reward a Carpenter

404 Not Found

最短経路出力する問題だと思って、それだとワーシャルフロイド法だと困るよなぁとか思ってダイクストラで解いて、提出した直後にただの最小コスト求める問題だったということに気づき絶望。

結局初めてやったダイクストラ法では必死にがんばって実装に2時間掛かり、ワーシャルフロイド法でやったら実装8分で終わった。

てかこれ、明らかにワーシャルフロイド法が最適な問題だっただろ。今思えば出題者もそれを意図してのノード数だったんだろうなっていう。

たしかに最初少ないなとは思ったけどただ単に最小コスト求める問題だと思ってなかったからスルーしてた。

ワーシャルフロイド法ソース

シンプル、キレイ

#include <iostream>
#include <cstdio>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
int main(){
	int wf[20][20];
	int n,m,a,b,c,d;
	cin >> n >> m;
	
	rep(i,n)rep(j,n)wf[i][j]=(1<<21);
	
	rep(i,m){
		scanf("%d,%d,%d,%d\n",&a,&b,&c,&d);
		a--;b--;
		wf[a][b] = c;
		wf[b][a] = d;
	}
	scanf("%d,%d,%d,%d\n",&a,&b,&c,&d);
	a--;b--;
	
	rep(k,n)rep(i,n)rep(j,n)wf[i][j]=min(wf[i][j],wf[i][k]+wf[k][j]);
	
	cout << c-d-wf[a][b]-wf[b][a] << endl;

}

ダイクストラ

汚い、リーディングハード。初めてやったdjkstraめちゃ汚い。効率悪い(枝狩り要素とか全く書いてない)可能性が。

#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;
typedef pair<int,int> NODE;

int dijk(int a,int b,int n, vector<vector<pair<int,int> > >info){
	priority_queue<NODE,vector<NODE>,greater<NODE> > Q;

	vector<NODE> node(n);
	for(int i=0;i<node.size();i++){
		node[i].first  = INT_MAX;
		node[i].second = i;
	}
	
	node[a].first = 0;	
	Q.push(node[a]);

	while(!Q.empty()){
		NODE now = Q.top();
		Q.pop();
		
		for(int i=0;i<info[now.second].size();i++){
			int to   = info[now.second][i].first;
			int cost = now.first + info[now.second][i].second;
			
			if(cost < node[to].first){
				node[to].first = cost;
				Q.push(node[to]);
			}
		}
	}
	return node[b].first;
}

int main(){
	int n,m,a,b,c,d;
	cin >> n >> m;
		
	vector< vector< pair<int,int> > > info(n);
	
	for(int i=0;i<m;i++){
		scanf("%d,%d,%d,%d\n",&a,&b,&c,&d);
		a--;b--;
		info[a].push_back( make_pair(b,c) );
		info[b].push_back( make_pair(a,d) );
	}

	scanf("%d,%d,%d,%d\n",&a,&b,&c,&d);
	a--;b--;

	cout << c - d - dijk(a,b,n,info) - dijk(b,a,n,info) << endl;
}