本文共 1277 字,大约阅读时间需要 4 分钟。
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define lowbit(x) (x&-x)#define e exp(1.0)#define eps 1e-8//ios::sync_with_stdio(false);// auto start = clock();// cout << (clock()-start)/(double)CLOCKS_PER_SEC< E[MAXN]进行初始化后加边 */const int INF=0x3f3f3f3f;const int MAXN=1000010;struct qnode{ int v; int c; qnode(int _v=0,int _c=0):v(_v),c(_c){} bool operator <(const qnode &r)const { return c>r.c; }};struct Edge{ int v,cost; Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}};vector E[MAXN];bool vis[MAXN];int dist[MAXN];void Dijkstra(int n,int start)//点的编号从1开始{ memset(vis,false,sizeof(vis)); for(int i=1;i<=n;i++)dist[i]=INF; priority_queue que; while(!que.empty())que.pop(); dist[start]=0; que.push(qnode(start,0)); qnode tmp; while(!que.empty()) { tmp=que.top(); que.pop(); int u=tmp.v; if(vis[u])continue; vis[u]=true; for(int i=0;i dist[u]+cost) { dist[v]=dist[u]+cost; que.push(qnode(v,dist[v])); } } }}void addedge(int u,int v,int w){ E[u].push_back(Edge(v,w));}int main()//刘哲{ int n,m;//n条边,m个点 cin>>n>>m; for(int i=0;i >a>>b>>c; addedge(a,b,c); } Dijkstra(n,1); cout<<"1到各点的距离为:"; for(int i=2;i<=n;i++)cout< <<' '; cout<
转载地址:http://teali.baihongyu.com/