85785


最小全域木問題のプリム法のプライオリティキューを使った方法で任意の入力をして結果を表示させたいが思うようにいきません。  
addEdgeにcinを挿入して実行してみましたが出力が上手くいきません。  
g.addEdge()のような形で入力の内容を代入できますか？解る方お願いします。

**入力:**

[code]

    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
    
[/code]

**期待する出力結果:** `cin` を用いて以下の出力にしたい。

[code]

    0 - 1
    1 - 2
    1 - 3
    5 - 4
    3 - 5
    3 - 6
    
[/code]

**現状の出力結果:** 入力結果を受け付けておらず、出力結果が予定通りでない。

[code]

    -1 - 0
    -1 - 1
    -1 - 2
    -1 - 3
    -1 - 4
    -1 - 5
    -1 - 6
    
[/code]

**ソースコード:**

[code]

    #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;
    }
    
[/code]


CC BY-SA 4.0
2022-01-17T14:11:07.923
85762
2022-01-19T07:58:02.147
2022-01-19T07:58:02.147
50767
50767
question
c++ アルゴリズム
最小全域木問題のプリム法のプライオリティキューを使った方法での入力と出力に関する問題
  
  
デバッグしてみたら出来ました。ありがとうございます。

[code]

    #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 addEdge(int from,int to,int cost);
        void prim();
    };
    Graph::Graph(int V)
    {
        this->V = V;
        adj = new List[V];
    }
    
    void Graph::addEdge(int from, int to, int 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 cur = 0;
        vector<int>key(V,INF);
        vector<int>parent(V, -1);
        vector<bool>used(V, false);
        Q.push(make_pair(0, cur));
        key[cur] = 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 = 1; i < V; i++) {
            cout << parent[i] <<" - " << i << endl;
        }
    }
    int main()
    {
        cin >> V >> E;
        Graph g(V);
        for (int i = 0; i < E; i++) {
            cin >> from >> to >> cost;
            g.addEdge(from, to, cost);
        }
        g.prim();
        return 0;
    }
    
[/code]


CC BY-SA 4.0
2022-01-19T01:22:51.250
85785
2022-01-19T02:56:01.893
2022-01-19T02:56:01.893
50767
50767
85762
answer