模板
Dijkstra
模板一（map数组模拟邻接表）
处理小图速度相对较快。
内存占用较小，对重边优化较差。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 1000;
int map[maxn][maxn];
int pre[maxn],dis[maxn];
bool vis[maxn];
int n,m;
void Dijkstra(int s)
{
memset(dis,0x3f,sizeof(dis));
memset(pre,-1,sizeof(pre));
memset(vis,false,sizeof(vis));
for(int i=1;i<=n;++i)
{
dis[i]=map[s][i];
pre[i]=s;
}
dis[s]=0;
vis[s]=true;
for(int i=2;i<=n;++i)
{
int mindist=INF;
int u=s;
for(int j=1;j<=n;++j)
if((!vis[j])&&dis[j]<mindist)
{
u=j;
mindist=dis[j];
}
vis[u] = true;
for(int j=1;j<=n;++j)
if((!vis[j]) && map[u][j] < INF){
if(map[u][j] + dis[u] < dis[j]){
dis[j] = map[u][j] + dis[u];
pre[j] = u;
}
}
}
}
模板二（链式前向星+优先队列优化）
主要优化在重边。因为使用了STL所以占用内存和速度相对较慢。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
const int INF=0x3f3f3f3f;
struct node
{
int d,u;
friend bool operator<(node a,node b)
{
return a.d>b.d;
}
node(int dist,int point):d(dist),u(point){}
};
struct Edge
{
int to,next;
int dist;
}edge[maxm];
int head[maxn],tot;
int pre[maxn],dis[maxn];
void init()
{
memset(head,-1,sizeof(head));
tot=0;
}
void addedge(int u,int v,int d)
{
edge[tot].to=v;
edge[tot].dist=d;
edge[tot].next=head[u];
head[u]=tot++;
}
void Dijkstra(int s)
{
priority_queue<node> q;
memset(dis,0x3f,sizeof(dis));
memset(pre,-1,sizeof(pre));
dis[s]=0;
while(!q.empty())
q.pop();
node a(0,s);
q.push(a); //起点入队列
while(!q.empty())
{
node x=q.top();
q.pop();
if(dis[x.u]<x.d) //最短路已找到
continue;
for(int i=head[x.u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(dis[v]>dis[x.u]+edge[i].dist)
{
dis[v]=dis[x.u]+edge[i].dist;
pre[v]=x.u;
q.push(node(dis[v],v));
}
}
}
}
模板三（结构体内置方法）
因为使用了链式前向星所以不担心重边。
其中还使用了快读方法，所以很快。
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <utility>
using namespace std;
const int N = 1005;
const int M = 1005;
const int INF = 0x3f3f3f3f
struct Graph{
struct Edge{
int v, w, next;
}edge[M];
int ehead[N];
void init(){
memset(ehead, -1, sizeof(ehead))
}
inline void addedge(int u, int v, int w){
edge[ecnt] = {v, w, ehead[u]};
ehead[u] = ecnt++;
}
int dist[N];
bool vis[N];
void Dijkstra(int s){
memset(dist, INF, sizeof(dist));
memset(vis, 0, sizeof(vis));
priority_queue<pair<int, int> > q;
q.push(make_pair(-(dist[s] = 0), s));
while(q.size()){
int u = q.top().second; q.pop();
if (vis[u]) continue;
vis[u] = true;
for (int i = ehead[u]; ~i; i = edge[i].next){
int v = edge[i].v;
if (vis[v]) continue;
int ndist = dist[u] + edge[i].w;
if (ndist < dist[v]) q.push(make_pair(-(dist[v] = ndist), v));
}
}
}
}g1, g2;
int Input(){
char c;
for (c = getchar(); c<'0' || c>'9'; c = getchar());
int a = c - '0';
for (c = getchar(); c >= '0' && c <= '9'; c = getchar())
a = a*10 + c - '0';
return a;
}
Floyd
代码很短，时间复杂度很高（O(n^3)）。
void floyd(){
for(int k=1; k<=n; ++k)
for(int i=1; i<=n; ++i)
for(int j=1; j<=n; ++j)
if (map[i][j] > map[i][k] + map[k][j]) //松弛
map[i][j] = map[i][k] + map[k][j];
}
Bellman-Ford
模板一（链式前向星）
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
struct Edge{
int u, v;
double r, c;
}edge[maxn*2];
double mostMoney[maxn];
int n, m, s;
double v;
int tot;
void addedge(int u, int v, double r, double c){
edge[tot].u = u;
edge[tot].v = v;
edge[tot].r = r;
edge[tot++].c = c;
}
bool relax(int n){
double temp = (mostMoney[edge[n].u] - edge[n].c)*edge[n].r;
if (temp > mostMoney[edge[n].v]){
mostMoney[edge[n].v] = temp;
return true;
}
return false;
}
bool bellman_ford(){
bool flag;
for (int i=0; i<n; i++) mostMoney[i] = 0.0;
mostMoney[s] = v;
for (int i=0; i<n-1; ++i){
flag = false;
for (int j=0; j<tot; ++j)
if (relax(j)) flag = true;
if (mostMoney[s] > v) return true;
if (!flag) return false;
}
for (int i=0; i<tot; ++i){
if (relax(i)) return true;
}
return false;
}
模板二
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
const int INF=0x3f3f3f3f;
struct Edge{
int u,v; //起点、终点
int dist; //长度
}edge[maxn];
int dis[maxn]; //最短距离数组
int n, m; //结点数、边数
bool Bellman_ford(int s){
memset(dis, INF, sizeof(dis));
dis[s]=0;
for(int k=1; k<n; ++k){ //迭代n-1次
for(int i=0; i<m; ++i){ //检查每条边
int x = edge[i].u, y = edge[i].v;
if(dis[x] < INF)
dis[y] = min(dis[y], dis[x] + edge[i].dist);
}
}
bool flag=1;
for(int i=0; i<m; ++i){ //判断是否有负环
int x = edge[i].u, y = edge[i].v;
if(d[y] > d[x] + edge[i].dist){
flag = 0; break;
}
}
return flag;
}
SPFA
模板一
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#define maxn 1000005
using namespace std;
const long long INF = 0xffffffff;
int Input(){
char c;
for (c = getchar(); c<'0' || c>'9'; c = getchar());
int a = c - '0';
for (c = getchar(); c>='0' && c<='9'; c = getchar()) a = a * 10 + c - '0';
return a;
}
int n, m;
struct edge{
int e, next, w;
}edge[2][maxn];
long long dis[maxn], ans;
int head[2][maxn], vis[maxn];
inline void spfa(int x){
for (int i=1; i<=n; i++){
dis[i] = 0xffffffff;
//cout << dis[i] << endl;
}
memset(vis, 0, sizeof(vis));
queue<int> q;
int a, b;
q.push(1);
vis[1] = 1;
dis[1] = 0;
while(!q.empty()){
a = q.front(); q.pop();
vis[a] = 1;
for (int i=head[x][a]; i != -1; i=edge[x][i].next){
b = edge[x][i].e;
if (dis[b] > dis[a] + edge[x][i].w){
dis[b] = dis[a] + edge[x][i].w;
if (!vis[b]) { q.push(b); vis[b] = 1; }
}
}
}
}
模板二
邻接矩阵
void spfa(int s){
for(int i=0; i<=n; i++) dis[i]=99999999; //初始化每点到s的距离
dis[s]=0; vis[s]=1; q[1]=s; //队列初始化,s为起点
int i, v, head=0, tail=1;
while (head<tail){ //队列非空
head++;
v=q[head]; //取队首元素
vis[v]=0; //释放队首结点，因为这节点可能下次用来松弛其它节点，重新入队
for(i=0; i<=n; i++) //对所有顶点
if (a[v][i]>0 && dis[i]>dis[v]+a[v][i]){
dis[i] = dis[v]+a[v][i]; //修改最短路
if (vis[i]==0){ //如果扩展结点i不在队列中，入队
tail++;
q[tail]=i;
vis[i]=1;
}
}
}
}
模板三
DFS优化
void spfa(int s){
for(int i=1; i<=b[s][0]; i++) //b[s,0]是从顶点s发出的边的条数
if (dis[b[s][i]>dis[s]+a[s][b[s][i]]){ //b[s,i]是从s发出的第i条边的另一个顶点
dis[b[s][i]=dis[s]+a[s][b[s][i]];
spfa(b[s][i]);
}
}
A - Til the Cows Come Home（POJ 2387）
题意
给出n个点和m条边，求从1到n的最短路。
思路分析
最短路裸题。如果用邻接表Dijkstra的话需要判重边。
Floyd和Bellman-ford不需要。
我用的是链式前向星+Dijkstra，所以也可以不判重。
代码
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 4005;
int T,N;
struct node {
int d,u;
friend bool operator < (node a, node b) {
return a.d > b.d;
}
node(int dist, int point): d(dist), u(point){}
};
struct Edge {
int to,next;
int dist;
} edge[maxn];
int head[maxn], tot;
int pre[maxn], dis[maxn];
void init() {
memset(head, -1, sizeof(head));
tot=0;
}
void addedge(int u,int v,int d) {
edge[tot].to = v;
edge[tot].dist = d;
edge[tot].next = head[u];
head[u]=tot++;
}
void Dijkstra(int s) {
priority_queue<node> q;
memset(dis, 0x3f, sizeof(dis));
memset(pre, -1, sizeof(pre));
dis[s]=0;
while(!q.empty()) q.pop();
node a(0,s);
q.push(a);
while(!q.empty()) {
node x = q.top(); q.pop();
if(dis[x.u] < x.d) continue;
for(int i = head[x.u]; i != -1; i = edge[i].next) {
int v = edge[i].to;
if (dis[v] > dis[x.u] + edge[i].dist) {
dis[v] = dis[x.u] + edge[i].dist;
pre[v] = x.u;
q.push(node(dis[v], v));
}
}
}
}
int main(){
init();
cin >> T >> N;
while (T--){
int u, v, d;
cin >> u >> v >> d;
addedge(u, v, d);
addedge(v, u, d);
}
Dijkstra(1);
cout << dis[N] << endl;
return 0;
}
B - Heavy Transportation（POJ 1797）
题意
给出从1城到n城的每条路的最大载重量，求最大运货量。
思路分析
最短路的变形题，只需要改一下松弛操作就可以了。
F - 地铁
CSU - 1808
题意
最短路。
给出n个地铁站，m条边，给出每条边的首尾地铁站a、b，和这条边所属的地铁线c，以及这条边的边权d。
地铁线之间需要换乘，换乘时间为abs(ci-cj)。
因为多了一个换乘时间，所以需要拆点。
用链式前向星存边，用map<int,int>拆点，用vector存当前点所在的地铁。
思路
首先读边。用map[u][x]来表示u地铁站在x号线上，存储一个标记值cnt，代表这个点是第几个点（重新编号）。然后取出这个点。v点同样。最后addedge两遍。
遍历所有点。对每个点下的vector排个序，这样就可以避免取绝对值。对每个点遍历vector，对于vector中的每条地铁线，将这个点取出添边。
制图之后就按照模板跑Dijkstra，注意最后获取结果的时候要跑一遍n点的vector找最小值。
代码
/******************************
*File name: csu1808.cpp
*Author: wzhzzmzzy
*Created Time: 一 4/17 20:54:29 2017
*TODO: CSU 1808 最短路
******************************/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;
const int maxn = 300005;
const int inf = 0x3f3f3f3f;
int n, m;
struct Edge{
int to, next;
int w;
}edge[maxn<<1];
int head[maxn], tot;
void init(){
memset(head, -1, sizeof(head));
tot = 0;
}
void addedge(int u, int v, int w){
edge[tot].to = v;
edge[tot].w = w;
edge[tot].next = head[u];
head[u] = tot++;
}
vector<int> num[maxn];
//某站所属的线路
map<int,int> mmp[maxn];
//某站是记录的第几个地铁站（拆点）
int dis[maxn], cnt;
struct node{
int now, c;
node(int _n=0, int _c=0):now(_n), c(_c){}
friend bool operator <(node a, node r){
return a.c > r.c;
}
};
void Dijkstra(){
priority_queue<node> q;
while (!q.empty()) q.pop();
for (int i = 1; i < cnt; ++i) dis[i] = inf;
for (int i = 0; i < num[1].size(); ++i){
int st = mmp[1][num[1][i]];
dis[st] = 0;
q.push(node(st, 0));
}
node temp;
while (!q.empty()){
temp = q.top(); q.pop();
int u = temp.now;
int cost = temp.c;
if (cost > dis[u]) continue;
for (int i = head[u]; ~i; i=edge[i].next){
int v = edge[i].to;
int w = edge[i].w;
if (dis[v] > cost+w){
dis[v] = cost + w;
q.push(node(v, dis[v]));
}
}
}
}
int main(){
int u, v, x, w;
while (~scanf("%d%d", &n, &m)){
init();
cnt = 1;
for (int i = 1; i <= n; ++i){
num[i].clear();
mmp[i].clear();
}
for (int i = 0; i < m; ++i){
scanf("%d%d%d%d", &u, &v, &x, &w);
if (!mmp[u][x]){
mmp[u][x] = cnt++;
num[u].push_back(x);
}
u = mmp[u][x];
if (!mmp[v][x]){
mmp[v][x] = cnt++;
num[v].push_back(x);
}
v = mmp[v][x];
addedge(u, v, w);
addedge(v, u, w);
}
for(int i = 1; i <= n; ++i){
sort(num[i].begin(), num[i].end());
for(int j = 0; j < num[i].size()-1; ++j){
u = mmp[i][num[i][j]];
v = mmp[i][num[i][j+1]];
w = num[i][j+1] - num[i][j]; //同一站点不同线路的拆点之间的差值
addedge(u, v, w);
addedge(v, u, w);
}
}
Dijkstra();
int ans = inf;
for (int i = 0; i < num[n].size(); ++i){
u = mmp[n][num[n][i]];
ans = min(ans, dis[u]);
}
printf("%d\n", ans);
}
return 0;
}
