## 静态邻接表的简单实现 原

N3verL4nd

``````#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
#pragma warning(disable : 4996)
const int MAXN = 1005;

typedef struct Node
{
int v;
int next;
}Node;
Node edge[MAXN];
int first[MAXN];
int n, m; //n点数 m边数

void init()
{
int x, y;
memset(first, -1, sizeof(first));
for (int i = 1; i <= m; i++)
{
cin >> x >> y;
edge[i].next = first[x];
edge[i].v = y;
first[x] = i;
}
}

void print()
{
for (int i = 1; i <= n; i++)
{
printf("%d", i);
for (int j = first[i]; j != -1; j = edge[j].next)
{
printf("->%d", edge[j].v);
}
printf("\n");
}
}

int main()
{
while (scanf("%d %d", &n, &m) != EOF)
{
init();
print();
}
return 0;
}``````

``````#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
#pragma warning(disable : 4996)
const int MAXN = 1005;

typedef struct Node
{
int v;//终点位置
int value;//权值
int next;//同一起点下在edge数组中的位置
}Node;
Node edge[MAXN];//邻接表
int first[MAXN];//以该点为起点的第一条边在edge数组中的位置
int n, m; //n点数 m边数

void init()
{
int x, y, value, index;
bool flag;
memset(first, -1, sizeof(first));
index = 1;
for (int i = 1; i <= m; i++)
{
scanf("%d %d %d", &x, &y, &value);
flag = false;
for (int j = first[x]; j != -1; j = edge[j].next)
{
if(y == edge[j].v)
{
if(value < edge[j].value)
{
edge[j].value = value;
}
flag = true;
break;
}
}
if(flag)
{
continue;
}
edge[index].v = y;
edge[index].value = value;
edge[index].next = first[x];
first[x] = index++;

swap(x, y);
edge[index].v = y;
edge[index].value = value;
edge[index].next = first[x];
first[x] = index++;
}
}

void print()
{
for (int i = 1; i <= n; i++)
{
printf("%d", i);
for (int j = first[i]; j != -1; j = edge[j].next)
{
printf("->%d", edge[j].v);
}
printf("\n");
}
}

int main()
{
while (scanf("%d %d", &n, &m) != EOF)
{
if(n == 0 && m == 0)
{
break;
}
init();
print();
}
return 0;
}``````

# 最短路

Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 19979    Accepted Submission(s): 8541

Problem Description

Input

Output

Sample Input
``````

2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0

``````

Sample Output
``````

3
2

``````

``````#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
#pragma warning(disable : 4996)
const int MAXN = 105;
const int INF = 999999;

typedef struct Node
{
int v;//终点位置
int value;//权值
int next;//同一起点下在edge数组中的位置
}Node;
Node edge[10005];//邻接表
int first[MAXN];//以该点为起点的第一条边在edge数组中的位置
int n, m; //n点数 m边数
bool visited[MAXN];
int dist[MAXN];
queue<int>Q;

void init()
{
int x, y, value, index;
bool flag;
memset(first, -1, sizeof(first));
index = 1;
for (int i = 1; i <= m; i++)
{
scanf("%d %d %d", &x, &y, &value);
flag = false;
for (int j = first[x]; j != -1; j = edge[j].next)
{
if(y == edge[j].v)
{
if(value < edge[j].value)
{
edge[j].value = value;
}
flag = true;
break;
}
}
if(flag)
{
continue;
}
edge[index].v = y;
edge[index].value = value;
edge[index].next = first[x];
first[x] = index++;

swap(x, y);
edge[index].v = y;
edge[index].value = value;
edge[index].next = first[x];
first[x] = index++;
}
}

void SPFA(int Start)
{
while (!Q.empty())
{
Q.pop();
}
memset(visited, false, sizeof(visited));
for (int i = 1; i <= n; i++)
{
dist[i] = INF;
}
dist[Start] = 0;
visited[Start] = true;
Q.push(Start);
while (!Q.empty())
{
int top = Q.front();
Q.pop();
visited[top] = false;
for (int i = first[top]; i != -1 ; i = edge[i].next)
{
int e = edge[i].v;
if(dist[e] > edge[i].value + dist[top])
{
dist[e] = edge[i].value + dist[top];
if(!visited[e])
{
Q.push(e);
visited[e] = true;
}
}
}
}
}

int main()
{
freopen("in.txt", "r", stdin);
while (scanf("%d %d", &n, &m) != EOF)
{
if(n == 0 && m == 0)
{
break;
}
init();
SPFA(1);
printf("%d\n", dist[n]);
}
return 0;
}``````

### N3verL4nd

【算法和数据结构】图（一）图的定义和封装（C++实现）

qq_28869927
2017/02/27
0
0

sea_ljf
2018/07/28
0
0
【译】Swift算法俱乐部-图

Andy_Ron
07/24
0
0

2018/08/28
3.6K
0

其实在上一篇介绍树结构的时候，已经有了一些算法的相关内容介入。而在图这种数据结构下，会有更多有关图的算法，比如广度优先搜索，深度优先搜索最短路径算法等等。这是我们要介绍的最后...

zaking
2018/05/05
0
0

mysql概览

8
0
golang微服务框架go-micro 入门笔记2.2 micro工具之微应用利器micro web

micro web micro 功能非常强大,本文将详细阐述micro web 命令行的功能 阅读本文前你可能需要进行如下知识储备 golang分布式微服务框架go-micro 入门笔记1:搭建go-micro环境, golang微服务框架...

6
0

8
0
Flutter 系列之Dart语言概述

Dart语言与其他语言究竟有什么不同呢？在已有的编程语言经验的基础上，我们该如何快速上手呢？本篇文章从编程语言中最重要的组成部分，也就是基础语法与类型变量出发，一起来学习Dart吧 一、...

5
0
rime设置为默认简体

zhenruyan

5
0