最短路--dijkstra

n个点，m条边，求1 - n 的距离 输入x y z，表示x到y的距离为z 输出1 - n的最短距离 不存在输出-1 //如果多次循环记得清空vector #include<cstdio> #include<queue> #include<vector> #include<algorithm> #include<cstring> using namespace std; #define INF 0x3f3f3f3f int dis[105]; int len[105][105]; int vis[105]; int n,m; vector<int>edge[105]; struct Pair { int fi,se; //fi 表示点，se表示距离 bool friend operator<(Pair a,Pair b) { return a.se>b.se; } }pr,ne; void dijkstra() { memset(dis,INF,sizeof(dis));//初始化数组为无穷大 memset(vis,0,sizeof(vis));//初始化数组为0 pr.fi=1; pr.se=0; priority_queue<Pair>q; q.push(pr); while(!q.empty()) { pr=q.top(); q.pop(); if(vis[pr.fi]) //判断点是否被标记 continue; vis[pr.fi]=1; //标记点 for(int i=0;i<edge[pr.fi].size();i++) { ne.fi=edge[pr.fi][i]; // edge[pr.fi][i]表示与pr.fi相连的第i+1个点 ne.se=pr.se+len[pr.fi][ne.fi]; if(ne.se<dis[ne.fi]) //判断是否是最短路径 { dis[ne.fi]=ne.se; q.push(ne); } } } } int main() { scanf("%d%d",&n,&m); memset(len,-1,sizeof(len)); for(int i=0;i<m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); edge[x].push_back(y); //储存边 edge[y].push_back(x); //无向图双向储存 if(len[x][y]==-1) //判断两个点之间是不是只有一条路 len[y][x]=len[x][y]=z; else len[y][x]=len[x][y]=min(z,len[x][y]);//如果有多条路储存长度较小的路 } dijkstra(); printf("%d",dis[n]==INF?-1:dis[n]); }