P:单源最短路径（简单版）
程序代码：
#includeiostream#includecstring#includevector#includecmathusingnamespacestd;constintN=5e5+5;constintG=1e4+5;intdis[G];boolvisited[G];intn,m,s;structNode{intto;//存储到哪intv;//存储权值};vectorNodevt[N];Nodeat;voidaddEdge(inta,intb,intc){at.to=b;at.v=c;vt[a].push_back(at);}//迪杰斯特拉求最短路径算法voiddijkstra(ints){memset(dis,0x3f,sizeof(dis));dis[s]=0;//初始中间节点//选择中间节点for(inti=1;in;i++){intk=-1;intMIN=0x3f3f3f3f;//离中间节点最近的点作为下一个中间节点for(intj=1;j=n;j++){if(visited[j]==0dis[j]MIN){MIN=dis[j];k=j;}}//万一不是连通图if(k==-1){return;//结束程序}//如果没有结束程序，说明找到第一个中间点visited[k]=1;//更新表格for(intj=0;jvt[k].size();j++){intg=vt[k][j].to;if(visited[g]==0dis[g]dis[k]+vt[k][j].v){dis[g]=dis[k]+vt[k][j].v;}}}}intmain(){cinnms;for(inti=0;im;i++){intu,v,w;cinuvw;addEdge(u,v,w);}dijkstra(s);for(inti=1;i=n;i++){if(dis==0x3f3f3f3f){cout"";}else{coutdis"";}}return0;}
P：租用游艇
程序代码：（dijkstra算法邻接矩阵方法）
#includeiostream#includecstringusingnamespacestd;inta[][];intvisited[],dis[];intn;voiddijkstra(){memset(dis,0x3f,sizeof(dis));dis[1]=0;for(inti=1;in;i++){intk=-1;intMIN=0x3f3f3f3f;for(intj=1;j=n;j++){if(visited[j]==0dis[j]MIN){MIN=dis[j];k=j;}}if(k==-1){return;}visited[k]=1;for(inti=1;i=n;i++){dis=min(dis,dis[k]+a[k]);}}}intmain(){cinn;memset(a,0x3f,sizeof(a));for(inti=1;i=n;i++){for(intj=i+1;j=n;j++){cina[j];}}dijkstra();//for(inti=1;i=n;i++){//coutdis"";//}coutdis[n]endl;return0;}一只小跃跃
