算法标签：

迪杰斯特拉

题解：

将公路系统抽象为图结构，交叉路口作为节点，道路作为边且边权为道路距离。先读取输入数据构建图，接着运用类似弗洛伊德算法计算每对交叉路口间的最短路径及路径中的下一个节点。对于每个标识牌位置，依据从标识牌前一个交叉路口到各城市的最短路径是否经过标识牌所在道路，筛选出应显示在标识牌上的城市。最后，将这些城市按照到标识牌前一交叉路口的四舍五入后的距离升序排列，距离相同则按城市名称字母顺序排列后输出，以满足标识牌信息展示的要求 。

#include <vector>
#include <iostream>
#include <iomanip>
#include <string>
using namespace std;

const int MAXN = 30;
const int MAXDIST = 100000000;
int distanc[MAXN][MAXN];//从交点a到b的最短距离 
int dist[MAXN][MAXN];//从交点a到b最段路径要经过的下一个交点 
int next_node[MAXN][MAXN];// 重命名为 next_node
string name[MAXN];//all the Cs that the shortest path from A to C will pass B. 
vector<int> passby[MAXN][MAXN];

//调试用方法， 打印二维数组的内容 
void ShowMatrix(int matrix[MAXN][MAXN], int rows, int cols) {
    int i, j;
    for (i = 0; i < rows; i++) {
        for (j = 0; j < cols; j++)
            cout << setw(11) << matrix[i][j] << " ";
        cout << endl << endl << endl;
    }
    cout << " ------------------------ " << endl;
}

//调试方法， 打印出从节点a 到 b的最段路径 
void FindPath(int a, int b) {
    while (a != b) {
        cout << a << "->";
        a = next_node[a][b];// 使用 next_node
    }
    cout << b << endl;
}

//对道路通往的城市排序 
//排序方法， 按 （距离， 城市名）排序 
void sortD(vector<int>& verc, int a, int b, int dis) {
    int i, j, di, dj, t;
    for (i = 0; i < verc.size(); i++) {
        for (j = i + 1; j < verc.size(); j++) {
            di = (dist[a][verc[i]] - dis + 50) / 100;
            dj = (dist[a][verc[j]] - dis + 50) / 100;
            if (di > dj || di == dj && name[verc[i]] > name[verc[j]]) {
                t = verc[i];
                verc[i] = verc[j];
                verc[j] = t;
            }
        }
    }
}

int main() {
    int n,/*Number of intersections*/
        m,/*Number of roads*/
        k,/*Number of cities*/ 
        s,/*Number of Signs*/
        a, b, dis, i, j;
    float d;
    // 使用cin读取输入
    cin >> n >> m >> k; 
    for (a = 0; a < n; a++)
        for (b = 0; b < n; b++)
            dist[a][b] = distanc[a][b] = MAXDIST;
    for (a = 0; a < n; a++)
        dist[a][a] = distanc[a][a] = 0;

    //读入铁路图信息 
    for (i = 0; i < m; i++) {
        cin >> a >> b >> d;
        dis = (int)(d * 100 + 0.5f); //加0.5避免浮点数精度错误 
        distanc[a][b] = distanc[b][a]
            = dist[a][b] = dist[b][a] = dis;
    }

    //读入城市名称 
    for (i = 0; i < k; i++) {
        cin >> a;
        cin >> name[a];
    }

    /************************************************************************/
    /* 以下程序段计算交点间最短路径并记录路径经由的下一个交点               */
    /************************************************************************/
    for (a = 0; a < n; a++)
        for (b = 0; b < n; b++)
            if (dist[a][b] < MAXDIST)
                next_node[a][b] = b; // 使用 next_node

    //Dijstra's algorithm. 
    for (s = 0; s < n; s++)
        for (a = 0; a < n; a++)
            if (dist[a][s] < MAXDIST)
                for (b = 0; b < n; b++)
                    if (dist[a][b] > dist[a][s] + dist[s][b])
                    {
                        dist[a][b] = dist[a][s] + dist[s][b];
                    }

    //最短路径下一步节点 
    for (a = 0; a < n; a++)
        for (b = 0; b < n; b++)
            if (a != b)
                for (s = 0; s < n; s++)
                    if (s != a && s != b && distanc[a][s] < MAXDIST
                        && dist[a][b] == dist[a][s] + dist[s][b])
                    {
                        next_node[a][b] = s; // 使用 next_node
                        break;
                    }

    for (a = 0; a < n; a++)
        for (b = 0; b < n; b++)
            if (a != b)
            {
                passby[a][next_node[a][b]].push_back(b); // 使用 next_node
            }

    cin >> s;
    for (i = 0; i < s; i++) {
        cin >> a >> b >> d;
        dis = (int)(d * 100 + 0.5f);
        sortD(passby[a][b], a, b, dis);
        for (j = 0; j < passby[a][b].size(); j++) {
            k = passby[a][b][j];
            if (name[k] != "")
                // 使用cout的正确格式化输出
                cout << left << setw(20) << name[k] 
                     << (dist[a][k] - dis + 50) / 100 << endl; 
        }
        cout << endl;
    }

    return 0;
}