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

全部评论

相关推荐

07-09 18:28
门头沟学院 Java
写着提前批,结果还要实习4个月以上???
程序员牛肉:这种不用看,直接投了,面试的时候问对应的HR就行。有可能他们是直接复制的暑期实习的模板。
点赞 评论 收藏
分享
昨天 11:05
门头沟学院 运营
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-10 14:10
啊啊啊啊好幸福,妈妈是我找工作发疯前的一束光
榕城小榕树:你是我见过最幸福的牛客男孩
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务