Dijkstra板子n^2（起点为0，而不是1）

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int n,m;//节点数和边数
int dis[105];//记录每个点到源点的距离
int mapi[105][105];//记录边
int vis[105];//记录这个点是否被选中过
void dijkstra(int s){//s是源点
    memset(dis,INF,sizeof(dis));
    memset(vis,0,sizeof(vis));
    int start = s;
    vis[start] = 1;
    dis[0] = 0;
    for(int i = 0;i < n;i++){
        dis[i] = min(dis[i],mapi[start][i]);
    }
    for(int i = 0;i < n-1;i++){
        int mini = INF;
        for(int j = 0;j < n;j++){
            if(vis[j]==0 && dis[j]<mini){
                mini = dis[j];
                start = j;
            }
        }
        vis[start] = 1;
        for(int k = 0;k < n;k++)
            dis[k] = min(dis[k],dis[start]+mapi[start][k]);
    }
}
int main()
{
    while(cin>>n>>m){
        memset(mapi,INF,sizeof(mapi));
        for(int i = 0;i < m;i++){
            int a,b,c;
            cin>>a>>b>>c;
            mapi[a][b] = c;
        }
        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                if(i == j)
                    mapi[i][j] = 0;
            }
        }
        dijkstra(0);
        for(int i = 0;i < n;i++)
            cout<<" "<<dis[i];
        cout<<endl;
    }
    return 0;
}

给出一组数据：

5 6

0 1 5

0 2 8

1 2 1

1 3 3

3 4 7

1 4 2

输出：0 5 6 8 7