#include<iostream> #include<queue> #include<cstdio> #include<cstring> #include<vector> using namespace std; #define N 505 #define inf 0x3f3f3f3f int path[N];//输出路径 存放的是i的前一个点 path[j]=u; int n,e,m,s; int vis[N],dis[N],mp[N][N]; int city[N];//为权值 第一优先级为最短路 第二优先级为权值最或者最小 此为第二类权值（和点相连） 还有一种权值为和路相连 那种更简单 int peo[N]; int pathnum[N];//最短路的条数！！！ 初始为1 只要在路径相同时累合即可 void dijkstra(int s) { memset(vis,0,sizeof vis); for(int i=0;i<n;i++) dis[i]=mp[s][i]; dis[s]=0; path[s]=-1; peo[s]=city[s]; pathnum[s]=1; //明确规定不加vis[s] for(int i=1;i<=n;i++) { int minn=inf,u=-1; for(int j=0;j<n;j++) if(!vis[j]&&minn>dis[j]) minn=dis[u=j]; if(u==-1)return; vis[u]=1; for(int j=0;j<n;j++) { if(dis[j]>dis[u]+mp[u][j]) { // pathnum[j]=pathnum[u];//最短路条数 dis[j]=dis[u]+mp[u][j]; path[j]=u; peo[j]=peo[u]+city[j]; } else if(dis[j]==dis[u]+mp[u][j]) { // pathnum[j]+=pathnum[u];//最短路条数 if(peo[j]<peo[u]+city[j]) { path[j]=u; peo[j]=peo[u]+city[j]; } } } } } void print(int x) { if(path[x]==-1) {printf("%d",x);return;} print(path[x]); printf(" %d",x); return ; } int main() { scanf("%d%d%d%d",&n,&m,&s,&e); for(int i=0;i<n;i++)scanf("%d",&city[i]); for(int i=0;i<n;i++) for(int j=0;j<n;j++) mp[i][j]=inf;//如果加上 i==j 时mp为0 则可以反复刷权值 while(m--) { int a,b,c; scanf("%d%d%d",&a,&b,&c); if(mp[a][b]>c)mp[a][b]=mp[b][a]=c; } dijkstra(s); printf("%d %d ", pathnum[e] ,peo[e] ); print(e); return 0; }
用堆优化
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define REP(i,N) for(int i=0;i<(N);i++) #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// #define inf 0x3f3f3f3f #define INF 0x3f3f3f3f #define N 3000 int head[N]; int pos; struct node { int v,to,nex; }edge[N<<4]; void add(int a,int b,int c) { edge[++pos].nex=head[a]; head[a]=pos; edge[pos].v=c; edge[pos].to=b; } struct Node { int d,id; bool operator<(Node b)const { return d>b.d; } }; int n; int dis[N],vis[N]; void dijkstra(int s) { rep(i,1,n) dis[i]=inf; dis[s]=0; priority_queue<Node>q; q.push(Node{0,s}); while(!q.empty()) { Node u=q.top();q.pop(); if(vis[u.id])continue; vis[u.id]=1; for(int i=head[u.id];i;i=edge[i].nex) { int v=edge[i].to; if(u.d+edge[i].v<dis[v]) { dis[v]=u.d+edge[i].v; q.push(Node{dis[v],v}); } } } } int main() { int m,s,t; RII(n,m);RII(s,t); while(m--) { int a,b,c; RIII(a,b,c); add(a,b,c); add(b,a,c); } dijkstra(s); cout<<dis[t]; return 0; }