最小全域木問題のプリム法のプライオリティキューを使った方法で任意の入力をして結果を表示させたいが思うようにいきません。
addEdgeにcinを挿入して実行してみましたが出力が上手くいきません。
g.addEdge()のような形で入力の内容を代入できますか?解る方お願いします。
入力:
7 9
0 1 1
1 2 2
1 3 3
1 5 7
2 4 10
3 5 1
3 6 5
4 5 5
5 6 8
期待する出力結果: cin
を用いて以下の出力にしたい。
0 - 1
1 - 2
1 - 3
5 - 4
3 - 5
3 - 6
現状の出力結果: 入力結果を受け付けておらず、出力結果が予定通りでない。
-1 - 0
-1 - 1
-1 - 2
-1 - 3
-1 - 4
-1 - 5
-1 - 6
ソースコード:
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const long long INF = 1e9;
typedef pair<int, int>P;
typedef vector<pair<int, int>>List;
int V, E;
int from, to, cost;
class Graph {
int V;
vector<pair<int, int>>*adj;
public:
Graph(int V);
void input();
void addEdge(int from,int to,int cost);
void prim();
};
Graph::Graph(int V)
{
this->V = V;
adj = new List[V];
}
void input() {
cin >> V >> E;
}
void Graph::addEdge(int from, int to, int cost) {
for (int i = 0; i < E; i++)
cin >> from >> to >> cost;
adj[from].push_back({ to,cost });
adj[to].push_back({ from,cost });
}
void Graph::prim() {
priority_queue<P, vector<P>, greater<P>>Q;
int src = 0;
vector<int>key(V,INF);
vector<int>parent(V, -1);
vector<bool>used(V, false);
Q.push(make_pair(0, src));
key[src] = 0;
while (!Q.empty())
{
int from = Q.top().second;
Q.pop();
if (used[from] == true) {
continue;
}
used[from] = true;
List::iterator i;
for (i = adj[from].begin(); i != adj[from].end(); i++)
{
int to = (*i).first;
int cost = (*i).second;
if (used[to] == false && key[to] > cost)
{
key[to] = cost;
Q.push(make_pair(key[to], to));
parent[to] = from;
}
}
}
for (int i = 0; i < V; i++) {
cout << parent[i] <<" - " << i << endl;
}
}
int main()
{
input();
Graph g(V);
g.addEdge(from,to,cost);
g.prim();
return 0;
}