Open UNICKCHENG opened 6 years ago
待更新题库
[任务] 用Dijkstra算法求单元最短路.图中不能有负权的边 [接口] 复杂度:O(n2) 输入: N 全局变量,图中的点数 g 全局变量,g[i][j]表示i到j之间边的距离 输出 dis 全局变量,dis[i]表示节点1到i的最短距离 const int maxn=1000; int dis[maxn],g[maxn][maxn],N; bool v[maxn];
[任务] 用Dijkstra算法求单元最短路.图中不能有负权的边 [接口] 复杂度:O(n2) 输入: N 全局变量,图中的点数 g 全局变量,g[i][j]表示i到j之间边的距离 输出 dis 全局变量,dis[i]表示节点1到i的最短距离
const int maxn=1000; int dis[maxn],g[maxn][maxn],N; bool v[maxn];
void dijkstra() { for(int i=1;i<=N;i++)dis[i]=INF; dis[1]=0; memset(v,0,sizeof(v)); for(int i=1;i<=N;i++) { int mark=-1,midis=INF; for(int j=1;j<=N;j++) { if(!v[j]&&dis[j]<mindis) { mindis=dis[j]; mark=j; } } v[mark]=1; for(int j=1;j<=N;j++) if(!v[j]) dis[j]=min(dis[j],dis[mark]+g[mark][j]); } }
## 题库 |ID|TITLE|CODE(C/C++)|备注| |:-:|:-:|:-:|:-:| |[POJ1502](http://poj.org/problem?id=1502)|MPI Maelstrom|||
Dijkstra
待更新题库
void dijkstra() { for(int i=1;i<=N;i++)dis[i]=INF; dis[1]=0; memset(v,0,sizeof(v)); for(int i=1;i<=N;i++) { int mark=-1,midis=INF; for(int j=1;j<=N;j++) { if(!v[j]&&dis[j]<mindis) { mindis=dis[j]; mark=j; } } v[mark]=1; for(int j=1;j<=N;j++) if(!v[j]) dis[j]=min(dis[j],dis[mark]+g[mark][j]); } }