前提・実現したいこと
深さ優先探索によって問題を解くプログラムを作成しました.
問題の大まかな内容は,n個のノードとm本の重み付きの無向辺が与えられたとき,その重みに矛盾があるかどうかを判定するというものです.
以下のソースコードは正しい挙動であることが確認されたのですが,
void dfs(const Graph &node, int N)
を
void dfs(Graph node, int N)
としたとき,実行時間が非常に長くなってしまいました.
const修飾子によって値の書き換えができなくなることと計算時間の短縮にどのような関係があるのでしょうか?
該当のソースコード
C++
1#include "bits/stdc++.h" 2using namespace std; 3#define MOD 1000000007 4#define FOR(i,a,b) for(int i=(a);i<(b);i++) 5#define REP(i,n) FOR(i,0,n) 6#define dump(x) cout << #x << " = " << (x) << endl; 7#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl; 8typedef long long ll; 9typedef pair<ll,ll> P; 10typedef vector<vector<P>> Graph; 11 12 13vector<int> dist(100010,MOD); 14bool f = true; 15 16void dfs(const Graph &node, int N){ 17 18 REP(i,node[N].size()){ 19 P p = node[N][i]; // ノードのエッジ情報をとる. 20 ll next = p.first; // 次のノード番号 21 22 if(dist[next] == MOD){ // 未訪問なら距離を計算 23 dist[next] = dist[N] + p.second; // 現在置に重みを加算 24 dfs(node,next); 25 } 26 27 else if(dist[next] != dist[N] + p.second){ // 訪問済みなら矛盾チェック 28 f = false; return; 29 } 30 31 } 32 33 return; 34} 35 36 37int main(){ 38 39 int n,m; 40 cin >> n >> m; 41 42 Graph node(n); 43 44 REP(i,m){ 45 int a,b,v; 46 cin >> a >> b >> v; 47 a--;b--; 48 node[a].push_back(P(b,v)); 49 node[b].push_back(P(a,-v)); 50 } 51 52 REP(i,n){ 53 if(dist[i] == MOD){ // 新しい部分木ならば,それを0に初期化 54 dist[i] = 0; 55 dfs(node,i); // 条件を満たさないと打ち切られる 56 } 57 } 58 59 if(f) 60 cout << "Yes" << endl; 61 else 62 cout << "No" << endl; 63 64 return 0; 65}
回答1件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。