Dijkstra學習筆記

暫時空白....
沒有前置，我用vector存圖

//存儲
struct edge{
    int w,to;//w是權值，to是連接到的下一條邊
};
vector<edge> e;
//連邊
...
for(int i=1;i<=m;i++)
{
    int to,s,w;
    scanf("%d%d%d",&s,&to,&w);
    edge tmp;
    tmp.to=to,tmp.w=w;
    e[s].push_back(tmp);//有向圖
    tmp.to=s;
    e[to].push_back(tmp);//無向圖
}

每一次用選取當前數組中dis中存儲的最小值的點，如果沒有訪問過，就可以訪問，

...
    for(int i=1;i<=n;i++)
    {
        int MIN=0x3f,now;
        for(int j=1;j<=n;j++)
        {
            if(vis[j]==0&&dis[j]<MIN)
            {
                MIN=dis[j];
                now=j;
            }
        }
        vis[now]=1;

並更新周圍的點

        for(int j=0;j<e[now].size();j++)
        {
            dis[e[now][j].to]=max(dis[now]+e[now][j].w,dis[e[now][j].to]);
            if(dis[now]+e[now][j].w<dis[e[now][j].to])
            {
                dis[e[now][j].to]=dis[now]+e[now][j].w;
            }
        }
    }

應該寫對了吧....因為我爆掉了qwq，而且似乎是RE?