dis[__]=0; // 源点距离初始化
for(int i=1;i<=n;i++){
int u=-1, best=INF;
for(int j=1;j<=n;j++)
if(!vis[j] && dis[j]<best){ best=dis[j]; u=j; }
if(u==-1) break;
__=1; // 标记 u 已确定最短路
for(每条边 u->v)
if(!vis[v] && dis[u]+w < dis[v]) dis[v]=dis[u]+w;
}
- 第 1 空(源点距离初始化)应填什么?答案:s(即 dis[s]=0)解析:源点到自身距离为 0。
- 第 2 空(标记已确定)应填什么?答案:vis[u]=1解析:每次选出未确定中距离最小的 u,标记为已访问(已确定最短路)。