HDOJ1874 畅通工程续 (Dijkstra)

题意分析

1. 某两点之间可能有多条通路，在跑Dij时需要用距离最小的算。
2. 当起点和重点相等的时候，距离为0
3. 点的编号从0开始。

2019年3月2日

改进版本，带路径的输出

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#define maxn 10010
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
int mp[maxn][maxn],vis[maxn],lowcost[maxn];
int pre[maxn],a[maxn];      //记录路径
int n,m,s,e;
void dijkstra(){
    for(int i=0;i<n;i++){
    lowcost[i]=mp[s][i];}lowcost[s]=0;vis[s]=1;for(int i=1;i<n;i++){
    int v=-1;int minn=inf;for(int j=0;j<n;j++){
    if(!vis[j]&&lowcost[j]<minn){
    minn=lowcost[j];v=j;}}if(v==-1) break;vis[v]=1;for(int j=0;j<n;j++){
    if(!vis[j]&&lowcost[j]>lowcost[v]+mp[v][j]){
    lowcost[j]=lowcost[v]+mp[v][j];pre[j]=v;}}}
}
int main(){
    std::ios::sync_with_stdio(false);while(cin>>n>>m){
    for(int i=0;i<n;i++){
    for(int j=0;j<n;j++) {
    mp[i][j]=inf;}mp[i][i]=0;}memset(vis,0,sizeof(vis));memset(lowcost,0,sizeof(lowcost));memset(pre,0,sizeof(pre));memset(a,0,sizeof(a));for(int i=0;i<m;i++){
    int x,y,z;cin>>x>>y>>z;if(mp[x][y]>z){
    mp[x][y]=mp[y][x]=z;}}cin>>s>>e;int cur=e;dijkstra();if(lowcost[e]==inf) cout<<"-1"<<endl;else {
    int pos=0;pre[s]=-1;while(pre[e]!=-1){
    a[pos++]=pre[e];e=pre[e];}for(int i=pos-1;i>=0;i--){
    cout<<a[i]<<" ";}cout<<cur<<endl;}}return 0;
}

（1）多组输入。

（2）这个地方还是没理解的那么清楚，开始提交了很多次都是WA。

		vis[v] = 1;			 //总是忘记标注已经访问if (v == -1) break;  //这里表示更新结束！！！

开始写成了

		vis[v] = 1;			 //总是忘记标注已经访问if (v == -1) return; 

然后认为一旦$v==?1$，就输出-1,这个思路是错误的。

应该在break后判断lowcost[e]是不是inf，从而判断是否存在最短路径。

//#include"pch.h"
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define maxn 10010
#define inf 0x3f3f3f
using namespace std;
typedef long long ll;
ll mp[maxn][maxn], vis[maxn], lowcost[maxn];
ll n, m;
ll s, e;	//起点和终点
void dijkstra() {
    for (int i = 0; i < n; i++) {
    lowcost[i] = mp[s][i];}vis[s] = 1;lowcost[s] = 0;for (int i = 1; i < n; i++) {
    ll minn = inf;int v = -1;for (int j = 0; j < n; j++) {
    if (!vis[j] && lowcost[j] < minn) {
    minn = lowcost[j];v = j;}}vis[v] = 1;			 //总是忘记标注已经访问if (v == -1) break;  //这里表示更新结束！！！for (int j = 0; j < n; j++) {
    //if (mp[v][j] == inf || lowcost[v] == inf) continue;if (!vis[j] && lowcost[j] > lowcost[v] + mp[v][j]) {
    lowcost[j] = lowcost[v] + mp[v][j];}}}
}
int main() {
    std::ios::sync_with_stdio(false);while (cin >> n >> m) {
    memset(vis, 0, sizeof(vis));memset(lowcost, 0, sizeof(lowcost));for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
    mp[i][j] = inf;}mp[i][i] = 0;}ll x,y,z;for (int i = 0; i < m; i++) {
    cin >> x >> y >> z;if (z < mp[x][y]) {
    mp[x][y] = mp[y][x] = z;}}cin >> s >> e;dijkstra();if (lowcost[e] == inf) cout << "-1" << endl;else cout << lowcost[e] << endl;}return 0;
}

题目给定了起点和终点，要求两点之间的最短距离。很明显的Dijkstra算法。（从源点到其余各顶点之间的最短路径）

Dijkstra算法（O^2）

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define maxn 3100using namespace std;
int n,m,x,y,z,sta,ed;
int mp[maxn][maxn],vis[maxn],lowcost[maxn];void dijkstra(int s){
    memset(vis,0,sizeof(vis));for(int i=0;i<n;i++) lowcost[i]=mp[s][i];vis[s]=1; lowcost[s]=0;for(int i=1;i<n;i++){
    int Min=inf;int v=-1;for(int j=0;j<n;j++){
    if(!vis[j]&&lowcost[j]<Min){
    Min=lowcost[j];v=j;}}vis[v]=1;                //这个我总是忘记写,vis[v]=1if(v==-1) break;         //这个非常重要，当时我没写wa了很久很久for(int j=0;j<n;j++){
    if(mp[v][j]==inf ||lowcost[v]==inf) continue;if(!vis[j]&&lowcost[j]>lowcost[v]+mp[v][j])lowcost[j]=lowcost[v]+mp[v][j];}}
}
int main(){
    while(cin>>n>>m){
    for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
    mp[i][j]=inf;}mp[i][i]=0; }for(int i=0;i<m;i++){
    cin>>x>>y>>z;if(z<mp[x][y]){
    mp[x][y]=mp[y][x]=z;}} cin>>sta>>ed;		//起点和终点 dijkstra(sta);printf("%d\n",lowcost[ed]==inf?-1:lowcost[ed]);}return 0;
}

Dijkstra算法（nlogn）优化

#include <stdio.h>
#include <queue>
#include <string.h>
#include <algorithm>
using namespace std;const int inf = 1<<30;
const int L = 1000+10;struct Edges
{
    int x,y,w,next;
};
struct node
{
    int d;int u;node (int dd = 0,int uu = 0):d(dd),u(uu) {
    }bool operator < (const node &x) const{
    return u>x.u;}
};priority_queue<node> Q;
Edges e[L<<2];
int head[L];
int dis[L];
int vis[L];void AddEdge(int x,int y,int w,int k)
{
    e[k].x = x,e[k].y = y,e[k].w = w,e[k].next = head[x],head[x] = k++;e[k].x = y,e[k].y = x,e[k].w = w,e[k].next = head[y],head[y] = k++;
}void init(int n,int m)
{
    int i;memset(e,-1,sizeof(e));for(i = 0; i<n; i++){
    dis[i] = inf;vis[i] = 0;head[i] = -1;}for(i = 0; i<2*m; i+=2){
    int x,y,w;scanf("%d%d%d",&x,&y,&w);AddEdge(x,y,w,i);}
}int Dijkstra(int n,int src)
{
    node mv;int i,j,k,pre;vis[src] = 1;dis[src] = 0;Q.push(node(src,0));for(pre = src,i = 1; i<n; i++){
    for(j = head[pre]; j!=-1; j=e[j].next){
    k = e[j].y;if(!vis[k] && dis[pre]+e[j].w<dis[k]){
    dis[k] = dis[pre]+e[j].w;Q.push(node(e[j].y,dis[k]));}}while(!Q.empty()&&vis[Q.top().d]==1)Q.pop();if(Q.empty())break;mv = Q.top();Q.pop();vis[pre=mv.d] = 1;}
}int main()
{
    int n,m,i,j,x,y;while(~scanf("%d%d",&n,&m)){
    init(n,m);scanf("%d%d",&x,&y);Dijkstra(n,x);printf("%d\n",dis[y]==inf?-1:dis[y]);}return 0;
}