1028. 路由器

#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f

int A[101][101];
map<string, int> B;
int n, m;

int final[101];
int dis[101];

// return the min index of dis array
int min_index() {
    int ret = -1;
    int min = INF;
    for (int i = 1; i <= n; i++) {
        if (final[i]) continue;
        if (dis[i] < min) {
            min = dis[i];
            ret = i;
        }
    }
    return ret;
}


int dijkstra(int x, int y) {
    memset(final, 0, sizeof(final));
    memset(dis, INF, sizeof(dis));
    int start = x;
    for (int i = 1; i <= n; i++) {
        dis[i] = A[start][i];
    }
    int min;
    while ((min = min_index()) != -1) {
        final[min] = true;
        // update dis array
        for (int j = 1; j <= n; j++) {
            if (dis[min] + A[min][j] < dis[j]) {
                dis[j] = dis[min] + A[min][j];
            }
        }
    }
    return dis[y];
}

int main() {
    memset(A, INF, sizeof(A));
    cin >> n >> m;
    string src, dest;
    int d;
    int index = 1;
    int x, y;
    for (int i = 0; i < m; ++i) {
        cin >> src >> dest >> d;
        if (B.count(src) == 0) {
            B[src] = index++;
        }
        if (B.count(dest) == 0) {
            B[dest] = index++;
        }
        x = B[src];
        y = B[dest];
        A[x][y] = d;
        A[y][x] = d;
    }

    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        cin >> src >> dest;
        x = B[src];
        y = B[dest];
        // 求x->y的最短距离
        int min_dis = dijkstra(x, y);
        cout << (min_dis >= INF ? -1 : min_dis) << endl;

    }


    int a = 0;
    return 0;
}

#include <iostream>
#include <string>
#include <map>
#include <queue>

using namespace std;
struct Vertex{
    string name;
    int price;
};
bool operator <(const Vertex a, const Vertex b)
{
    return a.price > b.price;
}

int main()
{
    int n,m;
    while (cin>>n>>m)
    {
        map<string, map<string, int> > graph;
        map<string, bool> visited;
        for(int i=0; i<m; i++)
        {
            string in,out;
            int weight;
            cin >> in >> out >> weight;
            graph[in][out] = weight;
            graph[out][in] = weight;
        }
        int num;
        cin >> num;

        while(num--)
        {
            string source,target;
            cin >> source >> target;

            if((graph.find(source)!=graph.end())&&(graph.find(target)!=graph.end()))
            {
                map<string, bool>::iterator it_visited;
                for(it_visited = visited.begin(); it_visited != visited.end(); it_visited++)
                    visited[it_visited->first] = false;

                int min_price = -1;
                priority_queue<Vertex> aux_queue;
                Vertex init_vertex = {source,0};
                aux_queue.push(init_vertex);
                while(!aux_queue.empty())
                {
                    Vertex cur_vertex = aux_queue.top();
                    aux_queue.pop();
                    visited[cur_vertex.name] = true;
                    if(cur_vertex.name == target)
                    {
                        min_price = cur_vertex.price;
                        break;
                    }
                    map<string, int>::iterator it;
                    for(it = graph[cur_vertex.name].begin(); it != graph[cur_vertex.name].end(); it++)
                    {
                        if(!visited[it->first])
                        {
                            Vertex next_vertex = {it->first, it->second+cur_vertex.price};
                            aux_queue.push(next_vertex);
                        }
                    }
                }
                cout<<min_price<<endl;
            }
            else
                cout<<"-1"<<endl;

        }

    }
    return 0;
}