dijk几种写法 HDU-2544例

//邻接矩阵 HDU - 2544 #include<iostream> #include<queue> #include<vector> #include<cstring> using namespace std; #define inf 0x3f3f3f3f int map[105][105]; //存图 int n,m; void dijk(int u,int v) { int dis[105]; for(int i=1;i<=n;i++) { dis[i]=map[u][i]; } int vis[105]={0}; vis[u]=1; //标记起点 for(int i=1;i<=n;i++) { int min=inf,o=-1; //找最小边 for(int j=1;j<=n;j++) { if(!vis[j]&&min>dis[j]) { min=dis[j]; o=j; } } if(o==-1) break; vis[o]=1; //标记 for(int j=1;j<=n;j++) //更新 { if(!vis[j]&&dis[j]>dis[o]+map[o][j]) { dis[j]=dis[o]+map[o][j]; } } } cout<<dis[v]<<endl; } int main() { while(cin>>n>>m) { if(n==0&&m==0) break; memset(map,inf,sizeof(map)); //初始化 把每一条路变为+++无限大 //初始化自己到自己距离为0 看要求写 for(int i=0;i<m;i++) { int u,v,val; cin >>u>>v>>val; map[u][v]=val; map[v][u]=val; //本题是无向图，所以正反存 } dijk(1,n); //1--->n } return 0; } ``//邻接表 HDU - 2544 #include<iostream> #include<queue> #include<vector> #include<cstring> using namespace std; #define inf 0x3f3f3f3f #define maxx 100+10 #define maxxx 40000 int n,m,p; int head[maxxx]; struct pp { int v,val,next; }ss[maxxx]; inline void add(int u,int v,int val) { ss[p].v=v; ss[p].val=val; ss[p].next=head[u]; head[u]=p++; } void dijk(int qi,int end) { int dis[maxxx]; memset(dis,inf,sizeof(dis)); queue<int>q; int vis[maxxx]={0}; vis[qi]=1; dis[qi]=0; q.push(qi); while(!q.empty()) { int t=q.front(); q.pop(); for(int i=head[t];i!=-1;i=ss[i].next) { if(ss[i].val+dis[t]<dis[ss[i].v]) {dis[ss[i].v]=ss[i].val+dis[t]; q.push(ss[i].v); } } } cout<<dis[end]<<endl; } int main() { while(cin>>n>>m) { if(n==0&&m==0) break; p=0; memset(head,-1,sizeof(head)); for(int i=0;i<m;i++) { int u,v,val; cin >>u>>v>>val; add(u,v,val);//本题是无向图，所以正反存 add(v,u,val); } dijk(1,n); //1--->n } }

// vector版 类邻接表 HDU - 2544 # include #include #include #include using namespace std; #define inf 0x3f3f3f3f #define maxx 100+10 #define maxxx 40000 struct pp { int v,val; }ss; vectorq[10005]; int n,m,p; void dijk(int qi,int end) {

int dis[maxxx]; memset(dis,inf,sizeof(dis)); queue<int>qq; dis[qi]=0; qq.push(qi); while(!qq.empty()) { int t=qq.front(); qq.pop(); for(int i=0;i<q[t].size();i++) { pp tt=q[t][i]; int val=tt.val; int v=tt.v; if(dis[v]>dis[t]+val) {dis[v]=dis[t]+val; qq.push(v); } } } cout<<dis[end]<<endl;

} int main() {

while(cin>>n>>m) { if(n==0&&m==0) break; p=0; for(int i=0;i<=n;i++) q[i].clear(); //清空vector for(int i=0;i<m;i++) { int u,v,val; cin >>u>>v>>val; ss.val=val; ss.v=v; q[u].push_back(ss); ss.v=u; q[v].push_back(ss); //本题是无向图，所以正反存 } dijk(1,n); //1--->n }

return 0; }

//vectot 加 priority_queue #include #include #include #include using namespace std; #define inf 0x3f3f3f3f #define maxx 100+10 #define maxxx 40000 struct pp { int v,val; }ss; struct node { int v,dis; node(int xx,int yy):v(xx),dis(yy){} bool friend operator<(const node a,const node b) { return a.dis>b.dis; } } ; vectorq[10005]; int n,m,p; void dijk(int qi,int end) {

int dis[maxxx],vis[maxxx]; memset(vis,0,sizeof(vis)); memset(dis,inf,sizeof(dis)); priority_queue<node>qq; dis[qi]=0; qq.push(node(qi,dis[qi])); while(!qq.empty()) { node t=qq.top(); qq.pop(); if(vis[t.v]) continue; vis[t.v]=1; for(int i=0;i<q[t.v].size();i++) { pp tt=q[t.v][i]; int val=tt.val; int v=tt.v; if(!vis[v]&&dis[v]>dis[t.v]+val) { dis[v]=dis[t.v]+val; qq.push(node(v,dis[v])); } } } cout<<dis[end]<<endl;

} int main() {

while(cin>>n>>m) { if(n==0&&m==0) break; p=0; for(int i=0;i<=n;i++) q[i].clear(); //清空vector for(int i=0;i<m;i++) { int u,v,val; cin >>u>>v>>val; ss.val=val; ss.v=v; q[u].push_back(ss); ss.v=u; q[v].push_back(ss); //本题是无向图，所以正反存 } dijk(1,n); //1--->n }

return 0; }

“`

效率最高的堆优化还是不会。。。，自己还是太菜！！！！