这个题把我搞抑郁了，并不是因为它难，而是自己的细节错误（近乎弱智），致使程序一直在出错。

先说下题意，这道题是比较典型的最短路问题，求两点间的最短距离然后输出交通所需的费用。我参考的

是Staginner的思路，也邪恶的参考的他的代码（我毕竟才第一次做这个，连dijkstra算法都不会）。

PS：他写得还是很不错的，先把代码贴出来：

注释是我的理解。这个算法在我看来是蛮耗时的，有O(N^3)，但是不难理解，就是三层循环不断更新i与j点的最小费用，

最后得出真正意义的最小费用就OK了，但是开始我也没想到这点，创新能力还是比较弱...fighting！

#include
      
        #include
       
        __int64 p[105],d[105][105];int main(){    int t,tt,n,m,a,b,i,j,k;    __int64 L1,L2,L3,L4,C1,C2,C3,C4,temp;    scanf("%d",&t);  // 居然是少写了这句，所以t成了随机数，编译通过了     for(tt = 1; tt <= t; tt ++)    {        scanf("%I64d%I64d%I64d%I64d%I64d%I64d%I64d%I64d",        &L1,&L2,&L3,&L4,&C1,&C2,&C3,&C4);         scanf("%d%d",&n,&m);        for(i = 0; i < n; i ++)            scanf("%I64d",&p[i]);             /*初始化费用d[i][j]，也可以认为是距离和费用的转换 */                   for(i = 0; i < n; i ++)            for(j = 0; j < n; j ++)            {                if(i == j) d[i][j] = 0; //  同一点木有距离                 else {                    temp = abs(p[i] - p[j]); //求两点距离                     if(temp <= L1)                        d[i][j] = C1;                    else if(temp <= L2)                         d[i][j] = C2;                    else if(temp <= L3)                        d[i][j] = C3;                    else if(temp <= L4)                        d[i][j] = C4;                    else if(temp > L4)                        d[i][j] = -1; //也可以定义成等于INF，当然INF需要足够大，至少大于100000000000                 }             }          /* FLOYD算法  */           for(k = 0; k < n; k ++) //k相当于中转站！             for(i = 0; i < n; i ++)                for(j = 0; j < n; j ++)                    if(d[i][k] != -1 && d[k][j] != -1) {        temp = d[i][k] + d[k][j];        if(temp < d[i][j] || d[i][j] == -1)  //注意到d[i][j] == -1才是真正的大距离                  d[i][j] = temp;                        }            printf("Case %d:\n",tt);    for(i = 0; i < m; i ++)    {         scanf("%d%d",&a,&b);     if(d[a-1][b-1] == -1)    printf("Station %d and station %d are not attainable.\n",a,b);    else    printf("The minimum cost between station %d and station %d is %I64d.\n",a,b,d[a-1][b-1]);  }    }    return 0;}