单源最短路径：
输入
4 4
0 1 1
0 3 1
1 3 1
2 0 1
输出
1 1
分析：
//分析题目：
//可转化为带权有向图求到顶点0的最短路径的问题
//若无路径，不输出，负责输出最短路径
代码分析在代码注释里面
单源最短路径：//分析题目：//可转化为带权有向图求到顶点0的最短路径的问题//若无路径，不输出，负责输出最短路径代码分析在代码注释里面#include<iostream>#include <algorithm>#include<string.h>#include<vector>//vector是一种动态数组，它拥有数组的所有功能并且能够动态增长using namespace std;#define INF 0xffffffstruct node{int x;int dis;}; vector<node> a[20005];//定义了一个容器的对象叫做a[i]，这个容器可以放node实体。int n,e,v,u;int dist[20005]; //从起点到i点的最短路径int visit[20005]; //记录是否访问 void Dijkstra(int v){fill(dist,dist + 20005,INF);//将dist数组的值全部设置为infdist[v] = 0;for(int i = 0;i < n;i ++){u = -1;int minx = INF;for(int j = 0;j < n;j ++){//逐个顶点访问if(visit[j] == 0 && dist[j] < minx){//找到dist数组中距离最小并且未被访问的点u = j;minx = dist[j];}}if(u == -1) break;visit[u] = 1;for(int i = 0;i < a[u].size();i ++){int x = a[u][i].x;//另x等于顶点v2if(visit[x] == 0 && dist[u] + a[u][i].dis < dist[x]){dist[x] = dist[u] + a[u][i].dis;}}}}int main(){cin >> n >> e;int b1,b2,b3;memset(visit,0,sizeof(visit));//将visit数组填充为0for(int i = 0;i < e;i ++){//逐个边添加cin >> b1 >> b2 >> b3;struct node temp = {b2,b3};a[b1].push_back(temp);//为a[b1]添加实体node} //可看作按照输入存储元素Dijkstra(v);for(int i = 1;i < n;i ++){if(dist[i] != INF){cout << dist[i] << " ";}} }
