迪杰斯特拉算法模板/三种图的存储模板 Single Source Shortest Path II Aizu - ALDS1_12_C

题目：

Single Source Shortest Path II

For a given weighted graph G=(V,E)

, find the shortest path from a source to each vertex. For each vertex u , print the total weight of edges on the shortest path from vertex 0 to u

.

Input

In the first line, an integer n

denoting the number of vertices in G is given. In the following n lines, adjacency lists for each vertex u

are respectively given in the following format:

u

k v1 c1 v2 c2 ... vk ck

Vertices in G

are named with IDs 0,1,...,n?1 . u is ID of the target vertex and k denotes its degree. vi(i=1,2,...k) denote IDs of vertices adjacent to u and ci denotes the weight of a directed edge connecting u and vi (from u to vi

).

Output

For each vertex, print its ID and the distance separated by a space character in a line respectively. Print in order of vertex IDs.

Constraints

• 1≤n≤10,000

题意：有一个有向带权图。

第一行输入n表示图的顶点数。

接下来n行输入图的邻接表。

每行第一个数字为顶点序号u（顶点序号范围【0，n-1】），第二个数字为与这个点相邻接的顶点数k。之后输入k组数据，每组数据由点to和权值weight组成，表示由u到这个点的边权值为weight。

邻接矩阵存储图：

#include<bits/stdc++.h>typedef long long ll;using namespace std;int n;
int G[10010][10010];
int minlen[10010];
bool vis[10010];void dijkstra(int p){memset(minlen,-1,sizeof(minlen));memset(vis,0,sizeof(0));minlen[p] = 0;while (1){int minp = -1;int minn = 1<<30;for(int i = 0 ; i<n ; i++){if(!vis[i] && minlen[i]!=-1 && minn>minlen[i]){minp = i;minn = minlen[i];}}if(minp == -1) break;vis[minp] = 1;for(int j = 0 ; j<n ; j++){if(!vis[j] && G[minp][j]!=1<<30){if(minlen[j] == -1){minlen[j] = minlen[minp]+G[minp][j];}else if( minlen[j] > minlen[minp]+G[minp][j]){minlen[j] = minlen[minp]+G[minp][j];}}}}
}int main(){ios::sync_with_stdio(false);cin>>n;for(int i = 0 ; i<n ; i++)for(int j = 0 ; j<n ; j++)G[i][j] = 1<<30;for(int t = 0 ; t<n ; t++){int u,k;cin>>u>>k;for(int i = 0 ; i<k ; i++){int to,weight;cin>>to>>weight;G[u][to] = weight;}}dijkstra(0);	for(int i = 0 ; i<n ; i++){cout<<i<<" "<<minlen[i]<<endl;}return 0;
}

邻接表存储图：

#include<bits/stdc++.h>typedef long long ll;using namespace std;int minlen[10010];
bool vis[10010];struct node{int to;int weight;node(int to,int weight){this->to = to;this->weight= weight;}
};
vector<node> G[10010];struct point{int p;int len;point(int p,int len){this->p = p;this->len = len;}friend bool operator< (point t1 , point t2){if(t1.len == t2.len)return t1.p > t2.p;return t1.len > t2.len; }
};void dijkstra(int p){memset(minlen,-1,sizeof(minlen));memset(vis,0,sizeof(0));priority_queue<point> q;q.push(point(p,0));minlen[p] = 0;while (!q.empty()){point temp = q.top();	q.pop();int now = temp.p;vis[now] = 1;if(minlen[now]!=-1 && minlen[now] < temp.len)continue;for(int i = 0 ; i<G[now].size() ; i++){int to = G[now][i].to;int len = G[now][i].weight;if(!vis[to]){if(minlen[to] == -1){minlen[to] = minlen[now] + len;q.push(point(to,minlen[to]));}else if(minlen[to] > minlen[now]+len){minlen[to] = minlen[now]+len;q.push(point(to,minlen[to]));}}}}
}int main(){ios::sync_with_stdio(false);int n;cin>>n;for(int t = 0 ; t<n ; t++){int u,k;cin>>u>>k;for(int i = 0 ; i<k ; i++){int to,weight;cin>>to>>weight;G[u].push_back(node(to,weight));}}dijkstra(0);	for(int i = 0 ; i<n ; i++){cout<<i<<" "<<minlen[i]<<endl;}return 0;
}

链式前向星存储图

#include<bits/stdc++.h>typedef long long ll;using namespace std;int n;
int head[10010];
struct{int to;int w;int next;
}mapp[500010];int minlen[10010];
bool vis[10010];struct node{int n;int len;node(const int n,const int len){this->n = n;this->len = len;}friend bool operator < (node f1, node f2){if(f1.len != f2.len)return f1.len > f2.len;return f1.n > f2.n; }
};void dijkstra(int p){memset(minlen,-1,sizeof(minlen));memset(vis,0,sizeof(0));priority_queue<node> q;minlen[p] = 0;vis[p] = 1;q.push(node(p,0));while (!q.empty()){node temp = q.top() ; q.pop();vis[temp.n] = 1;if( minlen[temp.n]!=-1 && minlen[temp.n]<temp.len)continue;int now = temp.n;for(int i = head[now] ; i!=0 ; i = mapp[i].next){int nxt = mapp[i].to;if(!vis[nxt]){if(minlen[nxt] == -1){minlen[nxt] = minlen[now]+mapp[i].w;q.push(node(nxt,minlen[nxt]));}else if(minlen[nxt] > minlen[now]+mapp[i].w){minlen[nxt] = minlen[now]+mapp[i].w;q.push(node(nxt,minlen[nxt]));}}}}}int main(){ios::sync_with_stdio(false);cin>>n;memset(head,0,sizeof(head));memset(mapp,0,sizeof(mapp));int num = 1;for(int t = 0 ; t<n ; t++){int u,k;cin>>u>>k;for(int i = 0 ; i<k ; i++){int to,weight;cin>>to>>weight;mapp[num].to = to;mapp[num].w = weight;mapp[num].next = head[u];head[u] = num;num++;}}dijkstra(0);	for(int i = 0 ; i<n ; i++){cout<<i<<" "<<minlen[i]<<endl;}return 0;
}