等待戈多-题解(C++代码)最短路spfa模板，它还没死！！！(逃

时间 = 路程 / 速度
#include "iostream"
#include "cstdio"
#include "cstdlib"
#include "cstring"
#include "cmath"
#include "algorithm"
#include "queue"
#include "vector"
#include "stack"
#include "map"
#include "set"
using namespace std;
typedef long long ll;
const int maxn = 510;
const int INF = 1e9;
int n, k;
double E[maxn][maxn];    //注意要用double的邻接矩阵
bool vis[maxn];          //判重数组
double d[maxn];          //double距离数组
/** 初始化距离数组 */
void init() {
    for(int i = 1; i <= n; ++i) {
        d[i] = INF;
    }
}
/** spfa核心代码（模板） */
void spfa() {
    init();        //初始化
    d[1] = 0;      //从1号结点开始，距离为0
    queue<int> q;
    q.push(1);
    while(!q.empty()) {
        int now = q.front();
        q.pop();
        vis[now] = false;
        for(int i = 1; i <= n; ++i) {
            //注意处理自环的边
            if(now != i && d[i] > d[now] + E[now][i]) {
                d[i] = d[now] + E[now][i];    //松弛
                if(!vis[i]) {
                    vis[i] = true;
                    q.push(i);
                }
            }
        }
    }
}
int main() {
    cin >> n >> k;
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n; ++j) {
            cin >> E[i][j];    //先读入路程
        }
    }
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n; ++j) {
            int val;
            cin >> val;
            if(!val) E[i][j] = INF;    //如果速度为0，就代表着自环或无法到达，权值给它个INF
            else E[i][j] /= val;    //时间 = 路程 / 速度
        }
    }
    spfa();
    printf("%.2f\n", d[k]);    //1 - k的距离就是d[k]
    return 0;
}