タクシー料金

質問する

一人でa時、一人でb時、
適当に追い風に乗って、なんとか最小の費用で家に帰る

の意見を打診

a点から全点までの最小距離,b点から全点までの最小距離を求める.
どこかで割るときはその割るところからa,bまでの最小距離を要求します~
簡単だと思いますが...ちょっと問題があります

質問です。

bfsの使用
一つの場所で合乗を放棄することもあります.
他の場所に拡散する方式で実現した

    //시작점에서 퍼지면서 여기서 쪼개져보고 저기서 쪼개져보면서 최저 값 찾기
    queue<pair<int, int>> q; //지금 지점, 지금까지 돈
    int check[205] = {0, };
    q.push({s,0});
    
    int answer = cost[s][0] + cost[s][1];
    
    while(!q.empty()){
        int nowNode = q.front().first;
        int nowCost = q.front().second;
        q.pop();
        
        //여기서 쪼개져도 보고
        answer = min(answer, nowCost + cost[nowNode][0] + cost[nowNode][1]);
        
        //다른 곳으로 넘어가기도 하구
        for(auto i:info[nowNode]){
            if(check[i.second]==0){
                check[i.second] = 1;
                q.push({i.second,nowCost+i.first});
            }
        }
    }

最初はなぜ間違っているのか分かりませんでしたが、
これは,ある点までの最小距離がbfsに拡散して求められないためである.
(もう一つの最短距離アルゴリズムがあるのは知っていますが...
この質問はどこまでだったのか~ここまで乗り合わせて~と思ってbfsを使いました…)
だから起点からすべての点までの最短距離も早めに求めました.

    for(int i = 1;i<=n;i++){
        answer = min(answer, cost[i][0] + cost[i][1] + cost[i][2]);
        cout << i << " " << cost[i][0] + cost[i][1] + cost[i][2] << "\n";
    }

こうして実現しました…!より簡潔で、清潔で、より良い...

質問です。

问题の例を见るだけで、ああ最短パスはMSTでも见つかる!
もう最短の長さのところまで来ているので他から来る必要はありません~~
そのままFremで解いたけどTeke...
だから調べてみると、フレムは1つの点からすべての最短距離を求めることができません.
なるほど~~ということでExtraを使いました!

コード#コード#

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>

using namespace std;

vector<pair<int, int>> info[205]; // index에서 first로 가는데 second만큼의 weight

int cost[205][3]; //a, b, s점에서의 모든 점의 거리 저장

void dijkstra(int startNode, int flag){
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    int check[205] = {0, };
    
    //시작점은 거리 0!
    cost[startNode][flag] = 0;
    //큐에 들어가서 퍼질 준비 됐으니까 1로 바꿔줘!
    check[startNode] = 1;
    pq.push({0, startNode});
    
    while(!pq.empty()){
        int nowNode = pq.top().second;
        int nowWeight = pq.top().first;
        pq.pop();
        
        for(auto i:info[nowNode]){
            int nextNode = i.second;
            int nextWeight = nowWeight + i.first;
            
            if(check[nextNode]==0){
                check[nowNode] = 1;
                // 현재 노드로 부터 연결된 엣지의 목적지까지 가는 거리와
                // 기존의 거리를 비교하여, 기존의 것이 더 크면 값을 갱신하고 더 탐색
                if (nextWeight < cost[nextNode][flag]) {
                    cost[nextNode][flag] = nextWeight;
                    pq.push({ nextWeight, nextNode });
                }
            }
        }
    }
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    //간선 정보를 인접 행렬로 저장
    for(vector<int> f: fares){
        info[f[0]].push_back({f[2], f[1]});
        info[f[1]].push_back({f[2], f[0]});
    }
    
    //다익스트라를 위해 거리를 아주 크게 초기화
    for(int i = 0;i<3;i++){
        for(int j = 1;j<=n;j++){
            cost[j][i] = 2000000000;
        }
    }
    
    //a집에서 모든 점의 거리, b집에서 모든 점의 최소 거리를 다익스트라로 구해!
    dijkstra(a, 0);
    dijkstra(b, 1);
    dijkstra(s, 2);
    
    int answer = cost[s][0] + cost[s][1];
    for(int i = 1;i<=n;i++){
        answer = min(answer, cost[i][0] + cost[i][1] + cost[i][2]);
        cout << i << " " << cost[i][0] + cost[i][1] + cost[i][2] << "\n";
    }
    
    return answer;
}