给你坐标最大为n,边数为m的无向边,输入m条,为x->y,长度为k

求起点(st)到终点(ed)的最短路径

dij()算法分析:

有三个数组,d[]用于记录最短路径,mp用于存储边,vis[]用于标记(标记过的点为已经计算出最短路径的点)

先重置vis[]

在对起点可以一次到达的位置载入到d[]中

设置d[0]=0(起点到起点自然为0)

标记vis[0]

寻找离起点最近的点(且没有被标记过的),然后标记它(已经求出最短距离)

然后更新其它与这个最近点有关的点

#include
    
     #include
     
      #include
      
       #include
       
        #define inf 0x3f3f3fusing namespace std;int n,st,ed,d,v;int mp[201][201];int vis[201],dis[201];void dij()///广度优先搜索思想{    memset(vis,0,sizeof(vis));    for(int i=1;i<=n;i++)///初始化原始路径(起始位置可以一次到达的点的距离)        dis[i]=mp[st][i];    dis[st]=0;    vis[st]=1;    for(int i=1;i<=n;i++)    {        int mins=inf;        for(int j=1;j<=n;j++)///用于寻找最近(小)的点且没有标记过的点        {            if(mins>=dis[j]&&!vis[j])                v=j,mins=dis[j];        }        vis[v]=1;            ///对该点进行标记(已经是最短距离)        for(int k=1;k<=n;k++)///更新其他点的最短距离(当前)            if(!vis[k])                dis[k]=min(dis[k],dis[v]+mp[v][k]);    }    if(dis[ed]>=inf) printf("-1\n");    else printf("%d\n",dis[ed]);}int main(){    while(scanf("%d",&n)&&n!=0)    {        memset(mp,inf,sizeof(mp));        memset(dis,0,sizeof(dis));        scanf("%d%d",&st,&ed);        dij();    }    return 0;}
       
      
     
    

 堆优化代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define inf 0x3f3f3f3f#define maxn 1024using namespace std;struct node{    int to,dis;    node (int a,int b){to=a,dis=b;}    friend bool operator <(node a,node b)    {        if(a.dis==b.dis) return a.to
         
          b.dis; }};vector
          
            mp[maxn];int dis[maxn],vis[maxn];int n,m,st,ed;void Dijkstra(){ memset(dis,inf,sizeof(dis)); dis[st]=0; priority_queue
           
             que; que.push(node(st,dis[st])); while(!que.empty()) { node x=que.top(); que.pop(); for(int i=0;i
            
             x.dis+y.dis) { dis[y.to]=x.dis+y.dis; que.push(node(y.to,dis[y.to])); } } } if(dis[ed]
            
           
          
         
        
       
      
     
    

: