#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<utility>
#include<iostream>
#include<algorithm>
//include<bits/stdc++.h>
using namespace std;
#define LL long long
#define MOD 1000000007
#define MAXN 100050
#define INF 0x3f3f3f3f
LL read()
{
LL w = 1, x = 0;
char ch = 0;
while (ch < ‘0‘ || ch>‘9‘)
{
if (ch == ‘-‘)
w = -1;
ch = getchar();
}
while (ch >= ‘0‘ && ch <= ‘9‘)
{
x = x * 10 + (ch - ‘0‘);
ch = getchar();
}
return w * x;
}
//int a=read();
template <class TT>
inline bool read(TT& ret)
{
char ch;
LL sgn;
if (ch = getchar(), ch == EOF)
{
return 0;
}
while (ch != ‘-‘ && (ch < ‘0‘ || ch>‘9‘))
{
ch = getchar();
}
sgn = (ch == ‘-‘) ? -1 : 1;
ret = (ch == ‘-‘) ? 0 : (ch - ‘0‘);
while (ch = getchar(), ch >= ‘0‘ && ch <= ‘9‘)
{
ret = ret * 10 + (ch - ‘0‘);
}
ret *= sgn;
return 1;
}
/*
while(read(a))
{
...
}
*/
定义与输入 Example:
pair<int, int>p;//头文件#include<utility>
cin >> p.first >> p.second;
比较：比较的时候，优先比较first大小，first相同时比较second。
还可以作为map的键值进行插入操作 Example:
int main()
{
map<string,int> mp;
mp.insert(pair<string,int>("help",1));
mp.insert(make_pair("hello",2));
for(map<string,int>::iterator it=mp.begin();it!=mp.end();it++)
{
cout<<it->first<<" "<<it->second<<endl;
}
return 0;
}
定义
set<int> s;
基本操作
s.begin() // 返回指向第一个元素的迭代器
s.clear() // 清除所有元素
s.count() // 返回某个值元素的个数（0或1）
s.empty() // 如果集合为空，返回true(真）
s.end() // 返回指向最后一个元素之后的迭代器，不是最后一个元素
s.erase() // 删除集合中的元素
s.find() // 返回一个指向被查找到元素的迭代器
s.insert() // 在集合中插入元素
s.lower_bound() // 返回指向大于（或等于）某值的第一个元素的迭代器
s.max_size() // 返回集合能容纳的元素的最大限值
s.size() // 集合中元素的数目
s.swap() // 交换两个集合变量
s.upper_bound() // 返回大于某个值元素的迭代器
定义
vector<int> s; // 定义一个空的vector对象
vector<int> s(n); // 定义一个含有n个int元素的vector对象
基本操作
s[i] // 直接以下标方式访问容器中的元素
s.front() // 返回首元素
s.back() // 返回尾元素
s.push_back(x) // 向表尾插入元素x
s.size() // 返回表长
s.empty() // 表为空时，返回真，否则返回假
s.pop_back() // 删除表尾元素
s.begin() // 返回指向首元素的随机存取迭代器
s.end() // 返回指向尾元素的下一个位置的随机存取迭代器
s.insert(it, val) // 向迭代器it指向的元素前插入新元素val
s.insert(it, n, val)// 向迭代器it指向的元素前插入n个新元素val
s.erase(it) // 删除由迭代器it所指向的元素
s.reserve(n) // 预分配缓冲空间，使存储空间至少可容纳n个元素
s.clear() // 删除容器中的所有元素
s.swap(v) // 将s与另一个vector对象进行交换
string可以看做是字符的vector，用法同上。
定义
stack<int> s;
基本操作
s.push(x); // 入栈
s.pop(); // 出栈
s.top(); // 访问栈顶
s.empty(); // 当栈空时，返回true
s.size(); // 访问栈中元素个数
定义
queue<int> q;
基本操作
q.push(x); // 入队列
q.pop(); // 出队列
q.front(); // 访问队首元素
q.back(); // 访问队尾元素
q.empty(); // 判断队列是否为空
q.size(); // 访问队列中的元素个数
定义
priority_queue <int> q;//默认降序队列
priority_queue <int,vector<int>,greater<int> > q;//升序队列，小顶堆
priority_queue <int,vector<int>,less<int> >q;//降序队列，大顶堆
基本操作
q.empty() // 如果队列为空，则返回true，否则返回false
q.size() // 返回队列中元素的个数
q.pop() // 删除队首元素，但不返回其值
q.top() // 返回具有最高优先级的元素值，但不删除该元素
q.push(item) // 在基于优先级的适当位置插入新元素
重载函数
struct nn{
int x,dis;
bool operator <(const nn& b)const//重载运算符‘<‘
{
return dis>b.dis;//顺序按照dis从小到大排（此处与sort的cmp恰好相反）
}
};
定义
map<string,int> mp;
基本操作
/* 向map中插入元素 */
m[key] = value;
m.insert(make_pair(key, value));
/* 查找元素 */
int i = m[key];
map<string, int>::iterator it = m.find(key);
/* 删除元素 */
m.erase(key); // 删除与指定key键值相匹配的元素对,并返回被删除的元素的个数。
m.erase(it); // 删除由迭代器it所指定的元素对,并返回指向下一个元素对的迭代器。
/* 其他操作 */
m.size(); // 返回元素个数
m.empty(); // 判断是否为空
m.clear(); // 清空所有元素
LL cnt, head[MAXN], d[MAXN];
struct node {
LL to, next, w;
};
node edge[MAXN*2];//双向图开两倍空间
void add(LL x, LL y, LL w)//双向图要调用两次
{
edge[++cnt].to = y;
edge[cnt].next = head[x];
edge[cnt].w = w;
head[x] = cnt;
}
复杂度$O(ElogE)$
dijkstra本质上的思想是贪心,它只适用于不含负权边的图.
LL n, m, s, wi, vi, ui, d[MAXN], head[MAXN], cnt;
struct node
{
LL to, next, w;
};
node edge[MAXN * 2];//开双倍大小
struct qnode
{
LL x, dis;
bool operator <(const qnode& b)const
{
return dis > b.dis;
}
}now,qt;
priority_queue<qnode> q;
qnode init(LL x, LL dis)
{
qnode ans;
ans.x = x;
ans.dis = dis;
return ans;
}
void add(LL x, LL y, LL z)
{
edge[++cnt].to = y;
edge[cnt].w = z;
edge[cnt].next = head[x];
head[x] = cnt;
}
void dij(LL s)
{
for (register LL i = 1; i <= n; i++)//初始化 注意n的意义
{
d[i] = 0x3f3f3f3f;
}
d[s] = 0;
now.x = s;
now.dis = 0;
q.push(now);
while (!q.empty())
{
now = q.top();
q.pop();
if (now.dis > d[now.x])
continue;
for (register LL i = head[now.x]; i; i = edge[i].next)
{
if (d[edge[i].to] > now.dis + edge[i].w)
{
qt.x = edge[i].to;
qt.dis = now.dis + edge[i].w;
d[edge[i].to] = now.dis + edge[i].w;
q.push(qt);
}
}
}
}
int main()
{
n = read();
m = read();
s = read();
for (register LL i = 1; i <= m; i++)
{
ui = read();
vi = read();
wi = read();
add(ui, vi, wi);
//add(vi,ui,wi); 注意是否是有向图
}
dij(s);
for (register LL i = 1; i <= n; i++)
{
if (i > 1)
{
cout << ‘ ‘;
}
cout << d[i];
}
cout << endl;
return 0;
}
LL cnt, head[MAXN], d[MAXN],n,m,ui,vi,wi;
struct node {
LL to, next, w;
};
node edge[MAXN * 2];//双向图开两倍空间
void add(LL x, LL y, LL w)//双向图要调用两次
{
edge[++cnt].to = y;
edge[cnt].next = head[x];
edge[cnt].w = w;
head[x] = cnt;
}
bool bellman_ford(LL s)
{
for (register int i = 1; i <= n; i++)//初始化 注意n的范围
{
d[i] = INF;
/*
如果想要单纯的判断所有图（即不保证图联通）中是否含有负环 可以将d[i]初始化为0
*/
}
d[s] = 0;
for (register int i = 1; i < n; i++)//最多松弛n-1次
{
bool ok = 0;
for (register int j = 1; j <= n; j++)//遍历所有边
{
if(d[j]==INF)//用来确保访问的点都是连通图
continue ;
for (register int k = head[j]; k; k = edge[k].next)
{
int x = j;
int y = edge[k].to;
int w = edge[k].w;
if (d[y] > d[x] + w)
{
d[y] = d[x] + w;
ok = 1;
}
}
}
if (!ok)
return 1;//无负环
}
for (register int j = 1; j <= n; j++)
{
for (register int k = head[j]; k; k = edge[k].next)
{
int x = j;
int y = edge[k].to;
int w = edge[k].w;
if (d[y] > d[x] + w)
{
return 0;
}
}
}
return 1;
}
//https://www.luogu.org/problem/P3366
#include<bits/stdc++.h>
using namespace std;
#define LL int
int read()
{
int x=0,w=1;
char ch=0;
while(ch<‘0‘||ch>‘9‘)
{
if(ch==‘-‘)
w=-1;
ch=getchar();
}
while(ch>=‘0‘&&ch<=‘9‘)
{
x=x*10+ch-‘0‘;
ch=getchar();
}
return w*x;
}
int n,m,cnt,tt;
struct node{
int x,y,z;
};
node edge[200005];
void add(int a,int b,int w)
{
edge[++cnt].x=a;
edge[cnt].y=b;
edge[cnt].z=w;
}
bool cmp(node a,node b)
{
return a.z<b.z;
}
int fa[5005];
int found(int x)
{
int pre;
int r=x;
while(fa[r]!=r)
{
r=fa[r];
}
while(x!=r)
{
pre=fa[x];
fa[x]=r;
x=pre;
}
return x;
}
bool ifin(int a,int b)
{
return found(a)==found(b);
}
void un(int a,int b)
{
int aa=found(a);
int bb=found(b);
fa[aa]=bb;
}
int ans,aa,bb,cc;
int main()
{
n=read();
m=read();
for(register int i=1;i<=n;i++)//并查集初始化
{
fa[i]=i;
}
for(register int i=1;i<=m;i++)
{
aa=read();
bb=read();
cc=read();
add(aa,bb,cc);
}
sort(edge+1,edge+cnt+1,cmp);//按照边从小到大排序
for(register int i=1;i<=cnt;i++)
{
if(tt==n-1)//tt记录已经在树中的边的个数 如果等于n-1说明建树完毕
break ;
if(!ifin(edge[i].x,edge[i].y))//如果该边连接的两点不在同一集合中 则合并
{
ans+=edge[i].z;
un(edge[i].x,edge[i].y);
tt++;
}
}
if(tt<n-1)//判断是否成功建树
{
cout<<"orz"<<endl;
}
else
{
cout<<ans<<endl;
}
return 0;
}
原文：https://www.cnblogs.com/lumingran/p/13996355.html