ACM-图论-最短路dijkstra poj1797模板题

本文主要是介绍ACM-图论-最短路dijkstra poj1797模板题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最短路的解法：
1.邻接矩阵//n比较小，点少边多（n^2)
2.邻接表//n比较大，点多边少(log n)
今天的代码是ACM/ICPC算法训练教程上的代码P209

优先队列+邻接表+局部dp判断+贪心的思想

题意分解：
1->n(iterator i)可以走的路中，可以运载的最大量是多少

//某条可行路的最小值,这条路中每个点的dis，随i的增加，dis[i]不断更新为整条路的最小值(优先队列处理）
//取所有条不同路中的最大值
//注意，要求输出有两个换行
//今天我只是代码的搬运工

#include<iostream>
#include<cstdio>
#include<queue>//优先队列 
using namespace std;
#include<algorithm>
#include<string.h>
#define inf 0x3f3f3f3f
int s,n,m,edge[1001][1001],dis[1001];
bool vis[1001];
//某条路的最小值,这条路中每个取小值< 
//取所有条不同路中的最大值 
struct node{int num;int val;//1到num的最大值 node(int nn=0,int vv=0):num(nn),val(vv){}bool operator <(const node &other)const{return val<other.val;} 
};
void dij(int start)//源点
{int i,j;node p;priority_queue<node>q;memset(vis,0,sizeof(vis));memset(dis,0,sizeof(dis));dis[start]=inf;vis[start]=1;q.push(node(start,dis[start]));//构造函数 for(i=0;i<n;i++){//求每一个的点距start的最小流p=q.top();q.pop();vis[p.num]=1;//p.num到下一（未全四周更新的）邻接点的距离更新 for(j=0;j<n;j++){if(!vis[j]&&dis[j]<min(dis[p.num],edge[p.num][j])){dis[j]=min(dis[p.num],edge[p.num][j]);q.push(node(j,dis[j]));}} //以i为起点的邻接表已经完成使命：更新dis[i的邻接点们]//优先队列！！！所以top一定是当前整条路的最小值 ///*这个只是我觉得：*/这时，判断有没有成环状的路！！！成环就不要这个点了。 while(!q.empty()&&vis[q.top().num])q.pop();if(q.empty())break;//中断，没有路/都是环状 }
} int main(){int i,j,a,p=1,t;scanf("%d",&t);while(t--){scanf("%d %d",&n,&m);memset(edge,0,sizeof(edge));while(m--){scanf("%d %d %d",&i,&j,&a);edge[i-1][j-1]=edge[j-1][i-1]=max(a,edge[i-1][j-1]);}printf("Scenario #%d:\n",p++);if(n==1)printf("%d\n\n",edge[0][0]);else {dij(0);printf("%d\n\n",dis[n-1]);}}return 0;
}