最短路
#include<bits/stdc++.h>
using namespace std;
const int INF = 1e6;
const int NUM =105;
struct edge{
int from,to,w;//from : 起点 to : 终点 w:权值
edge(int a,int b,int c){from = a;to = b;w = c;}
};
vector<edge>e[NUM];
struct s_node{
int id,n_dis;//id:结点 n_dis:结点到起点的距离
s_node(int b,int c){
id = b;
n_dis = c;
}
bool operator<(const s_node &a)const{
return n_dis>a.n_dis;
}
};
int n,m;
int pre[NUM];//前驱结点
/*void print_path(int s,int t){
if(s==t) {printf("%d",s);return ;}
print_path(s,pre[t]);
printf("%d",t);
}*/
void dijkstra(){
int s = 1;
int dis[NUM]; //记录所有的结点到起点的距离
bool done[NUM];//done[i]=true表示到结点i的最短路径已经找到
for(int i=1;i<=n;i++){dis[i]=INF;done[i]=false;}
dis[s]=0;//起点到自己的距离的为0
priority_queue<s_node>Q;//优先队列储存结点信息
Q.push(s_node(s,dis[s]));//起点先进队
while(!Q.empty()){
s_node u = Q.top();//pop出起点距离最小的结点
Q.pop();
if(done[u.id]) continue;//丢弃找到最短路径的结点，即集合A中的结点
done[u.id] = true;
for(int i=0;i<e[u.id].size();i++){ //检查结点u的所有邻居
edge y = e[u.id][i]; //u.id的第i个邻居是y.to
if(done[y.to]) continue; //丢弃已经找到最短路径的邻居结点
if(dis[y.to]>y.w+u.n_dis){
dis[y.to] = y.w +u.n_dis;
Q.push(s_node(y.to,dis[y.to]));
//扩展新的邻居结点，放到优先队列中
//pre[y.to] = u.id;
//如果有需要就记录路径
}
}
}
printf("%d\n",dis[n]);
//print_path(s,n);
}
int main(){
while(cin>>n>>m){
if(n==0&&m==0) return 0;
for(int i = 1;i <= n;i++) e[i].clear();
while(m--){
int a,b,c;
cin>>a>>b>>c;
e[a].push_back(edge(a,b,c));//a结点的邻居全放在e[a]
e[b].push_back(edge(b,a,c));
}
dijkstra();
}
}
/*5 6
1 2 2
1 3 3
1 4 3
3 5 3
4 5 2
2 5 6
*/ 题意：有n个点，求1到其他所有点的最短路之和加上所有点到1号点的最短路之和
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e9;
const ll NUM =1000005;
struct edge{
int to,next,w;//i就是起点，to是终点，next下一条边，w权值
}edge[NUM],edge2[NUM];
struct s_node{
int id,n_dis;//id:结点 n_dis:结点到起点的距离
s_node(int b,int c){
id = b;
n_dis = c;
}
bool operator<(const s_node &a)const{
return n_dis>a.n_dis;
}//路径小的先出队
};
int n,m,cnt,cnt1;
int head[NUM],head1[NUM];
int pre[NUM];//前驱结点
/*void print_path(int s,int t){
if(s==t) {printf("%d",s);return ;}
print_path(s,pre[t]);
printf("%d",t);
}*/
void addedge(int u,int v,int w){
edge[cnt].to=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt++;
}//链式前向星存图
void addedge2(int u,int v,int w){
edge2[cnt1].to=v;
edge2[cnt1].w=w;
edge2[cnt1].next=head1[u];
head1[u]=cnt1++;
}
ll dis[NUM]; //记录所有的结点到起点的距离
bool done[NUM];//done[i]=true表示到结点i的最短路径已经找到
ll dijkstra(int s){
for(int i=1;i<=n;i++){dis[i]=INF;done[i]=false;}
dis[s]=0;//起点到自己的距离的为0
priority_queue<s_node>Q;//优先队列储存结点信息
Q.push(s_node(s,dis[s]));//起点先进队
while(!Q.empty()){
int u = Q.top().id;//pop出起点距离最小的结点
Q.pop();
if(done[u]) continue;//丢弃找到最短路径的结点，即集合A中的结点
done[u] = true;
for(int i=head[u];~i;i=edge[i].next){ //利用head回溯，检查结点u的所有邻居
int y = edge[i].to,w=edge[i].w;//u.id的第i个邻居是y.to
if(done[y]) continue; //丢弃已经找到最短路径的邻居结点
if(dis[y]>dis[u]+w){
dis[y] = dis[u]+w;
Q.push(s_node(y,dis[y]));
//扩展新的邻居结点，放到优先队列中
//pre[y.to] = u.id;
//如果有需要就记录路径
}
}
}
ll sum=0;
for(int i=1;i<=n;i++) sum+=dis[i];
return sum;
}
ll dijkstra1(int s){
for(int i=1;i<=n;i++){dis[i]=INF;done[i]=false;}
dis[s]=0;//起点到自己的距离的为0
priority_queue<s_node>Q;//优先队列储存结点信息
Q.push(s_node(s,dis[s]));//起点先进队
while(!Q.empty()){
int u = Q.top().id;//pop出起点距离最小的结点
Q.pop();
if(done[u]) continue;//丢弃找到最短路径的结点，即集合A中的结点
done[u] = true;
for(int i=head1[u];~i;i=edge2[i].next){ //利用head回溯，检查结点u的所有邻居
int y = edge2[i].to,w=edge2[i].w;//u.id的第i个邻居是y.to
if(done[y]) continue; //丢弃已经找到最短路径的邻居结点
if(dis[y]>dis[u]+w){
dis[y] = dis[u]+w;
Q.push(s_node(y,dis[y]));
//扩展新的邻居结点，放到优先队列中
//pre[y.to] = u.id;
//如果有需要就记录路径
}
}
}
ll sum=0;
for(int i=1;i<=n;i++) sum+=dis[i];
return sum;
}
int main(){
int t;
cin>>t;
while(t--){
memset(head,-1,sizeof(head));
memset(head1,-1,sizeof(head1));
cnt=cnt1=0;
cin>>n>>m;
for(int i = 1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
addedge(u,v,w);
addedge2(v,u,w);
}
printf("%lld\n",dijkstra(1)+dijkstra1(1));
}
}hdu2544 最短路
链式前向星
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const ll N = 1e4 + 7;
int Next[N] , to[N] , head[N] , val[N];
int dis[N] , done[N];
int tot;
struct node{
int u , n_dis;
node(int a, int b){u = a , n_dis = b;}
bool operator<(const node& a) const{
return n_dis > a.n_dis;
}
};
void addedge(int u , int v ,int w){
to[++tot] = v;
val[tot] = w;
Next[tot] = head[u];
head[u] = tot;
}
int n , m;
void dijstra(int s){
memset(dis, 0x3f3f3f3f , sizeof(dis));
memset(done , 0 ,sizeof(done));
priority_queue<node>q;
dis[s] = 0;//到自己的距离为0
q.push({s , dis[s]});
while(q.size()){
int u = q.top().u; q.pop();
if(done[u]) continue;
done[u] = 1;
for(int i = head[u] ; i ; i = Next[i]){
int v = to[i] , w = val[i];
if(done[v]) continue;
if(dis[v] > dis[u] + w){
dis[v] = dis[u] + w;
q.push({v , dis[v]});
}
}
}
cout<<dis[n]<<endl;
}
int main()
{
while(~scanf("%d%d" , &n , &m)){
if(n == 0 && m == 0) break;
tot = 0;
memset(Next, 0, sizeof(Next));
memset(head, 0, sizeof(head));
for(int i = 1; i <= m ; i++){
int u , v ,w;
cin>>u>>v>>w;
addedge(u , v , w);
addedge(v , u , w);
}
dijstra(1);
}
return 0;
}
图论 文章被收录于专栏
难顶
