差旅问题（邻接矩阵，迪杰斯特拉算法？）

大一，第一次接触数据结构，完全不精通。猜测用邻接矩阵存储各节点间边的权值。但是如何使用邻接矩阵图对于我比较困难，想请教一下大家。具体如图：

应该是一道题，给你一个例子参考https://www.cnblogs.com/xiaoshiwang/p/9442391.html

就是一个最短路径问题呀

最短路问题（4种方法）（邻接矩阵，邻接表，bellman-ford,spfa)
https://blog.csdn.net/nhl19961226/article/details/54580847

#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
#define inf 0x3f3f3f3f
#define maxx 5009
using namespace std;
struct ndoe
{
    int u,v,w;
    int next;
}dis[maxx];
int first[maxx];
int dp[maxx];//记录最短路
int xia[maxx];//该点是否在队列中
int M;
void set_dis(int u,int v,int w)//建立邻接表
{
    dis[M].u=u;
    dis[M].v=v;
    dis[M].w=w;
    dis[M].next=first[u];
    first[u]=M++;
}
int main()
{
    int m,n;
    while(~scanf("%d%d",&m,&n))
    {
        M=0;
        memset(first,-1,sizeof(first));
        memset(xia,0,sizeof(xia));
        memset(dp,inf,sizeof(dp));
        for(int i=1; i<=m; i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            set_dis(a,b,c);
            set_dis(b,a,c);
        }
        dp[1]=0;//初始化
        xia[1]=1;
        queue<int>q;
        q.push(1);//先将起始点放入队列中
        int x;
        while(!q.empty())
        {
            x=q.front();
            q.pop();
            xia[x]=0;
            for(int j=first[x]; j!=-1; j=dis[j].next)
            {
                if(dp[dis[j].v]>dp[x]+dis[j].w)
                {
                    dp[dis[j].v]=dp[x]+dis[j].w;
                    if(xia[dis[j].v]==0)//这个点被松弛过，所以也可以松弛别的点，放入队列中
                    {
                        q.push(dis[j].v);
                        xia[dis[j].v]=1;
                    }
                }
            }
        }
        printf("%d\n",dp[n]);
    }
    return 0;
}