计算单源最短路 不能计算负环
邻接矩阵
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
typedef long long ll;
#define MAX 1005
#define inf 0x3f3f3f3f
int dist[MAX];
int a[MAX][MAX];
int vis[MAX];
int n;
void dijkstra(int vs) //计算单元最短路
{int i,j,k;for(i=1;i<=n;i++)dist[i] = a[vs][i];memset(vis,0,sizeof(vis));dist[vs] = 0;vis[vs] = 1;for(i=1;i<=n;i++){int minn = inf;for(j=1;j<=n;j++)//寻找当前距离图最近的点{if(!vis[j]&&dist[j] < minn){minn = dist[j];k = j;}}vis[k] = 1;for(j=1;j<=n;j++)//把点放入图中 更新未获得最短路径的点 松弛操作{if(!vis[j]&&dist[j] < dist[k] + a[k][j]);{vis[j] = dist[k] + a[k][j];}}}
}
int main()
{int m,i,j;scanf("%d%d",&n,&m);for(i=1;i<=n;i++) //初始化图{for(j=1;j<=n;j++){if(i==j) a[i][j] = 0;else a[i][j] = inf;}}int u,v,w;for(i=1;i<=m;i++){scanf("%d%d%d",&u,&v,&w);if(a[u][v] > w){a[u][v] = w;a[v][u] = w;}}dijkstra(1);printf("%d\n",dist[n]);return 0;
}
邻接表
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <cstring>using namespace std;
typedef long long ll;
#define MAX 1005
#define inf 0x3f3f3f3f
int dist[MAX];
int u[MAX],v[MAX],w[MAX];
int next[MAX];//开边的大小
int first[MAX];
int vis[MAX];
int n;
void dijkstra(int vs) //计算单源最短路
{int i,j,k;memset(vis,0,sizeof(vis));for(i=1;i<=n;i++) dist[i] = inf;queue<int> q;dist[vs] = 0;vis[vs] =1;q.push(vs);while(!q.empty()){int x = q.front();q.pop();for(i=first[x];i!=-1;i = next[i]){if(!vis[v[i]]&&dist[v[i]] > dist[x] + w[i]){dist[v[i]] = dist[x] + w[i];q.push(v[i]);}}vis[x] = 0;}
}
int main()
{int m,i,j;scanf("%d%d",&n,&m);for(i=1;i<=n;i++) //初始化图{first[i] = -1;}for(i=1;i<=m;i++){scanf("%d%d%d",&u[i],&v[i],&w[i]);next[i] = first[u[i]];first[u[i]] = i;}dijkstra(1);printf("%d\n",dist[n]);return 0;
}