渣渣先开个头, 给自己在网上找几个大神模板, 免得做到题目不会
- (自己写是不可能自己写的, 自己写是 ac 不了的)
- -----------------------
三种算法: Dijkstra,spfa,bellmanford(Dijkstra 加堆优化没学清楚, 先不加进来了)
时间复杂度: Dijkstra:O(n²) (没有负权时使用)
- spfa:O(V*E) (有负权无负圈, 但是能检测负圈)
- bellmanford:O(V*E) (有负值, 有负圈)
- Dijkstra:
- #include<bits/stdc++.h>
- using namespace std;
- const int INF = 0x3F3F3F3F;
- const int N = 1005;
- int m, n, st, mp[N][N];
- int dis[N], vis[N];
- void init() {
- for (int i=1; i<=n; i++) {
- for (int j=1; j<=n; j++) {
- if (i == j) mp[i][j] = 0;
- else mp[i][j] = INF;
- }
- dis[i]=INF;
- }
- }
- void creatgraph() {
- int t1, t2, t3;
- for (int i=0; i<m; i++) {
- scanf("%d%d%d", &t1, &t2, &t3);// 两个顶点和权值
- if (mp[t1][t2]> t3)// 防止重复输入相同节点, 但是权值不同
- mp[t1][t2] = t3;
- //mp[t2][t1] = t3;
- }
- }
- void dijkstra(int st) {
- memset(vis, 0, sizeof(vis));
- for (int i=1; i<=n; i++) dis[i] = mp[st][i];
- vis[st] = 1;
- for (int i=1; i<=n-1; i++) { // 循环 n-1 次
- /* 找出离起点最近的点 */
- int minn = INF, k = -1;
- for (int j=1; j<=n; j++) {
- if (!vis[j] && dis[j]<minn) {
- minn = dis[j];
- k = j;
- }
- }
- if(k==-1) break;
- vis[k] = 1;
- for (int j=1; j<=n; j++) { // 松弛操作, 找到媒介使得出现新的最短路
- if (!vis[j] && dis[k]+mp[k][j] <dis[j])
- dis[j] = dis[k] + mp[k][j];
- }
- }
- }
- int main() {
- scanf("%d%d%d", &n, &m, &st); //n 个顶点, m 条边
- init(); // 初始化地图
- creatgraph(); // 建图
- dijkstra(st);
- for(int i=1; i<=n; i++) {
- if(i==1) printf("%d", dis[i]);
- else printf("%d", dis[i]);
- }
- }
- // 摘自 https://blog.csdn.net/Scar_Halo/article/details/82825418
- spfa:
- #include
- #include
- #include
- #include
- #include
- using namespace std;
- const int maxn=300001;
- const int inf =0x7ffffff;
- struct edge
- {
- int from,to,w,next;
- }e[1000001];
- int head[maxn];
- int vis[maxn];
- int dist[maxn];
- int n,m,t;
- void add(int i,int j,int w)
- {
- e[t].from=i;
- e[t].to=j;
- e[t].w=w;
- e[t].next=head[i];
- head[i]=t++;
- }
- void spfa(int s)
- {
- queue q;
- for(int i=1;i<=n;i++)
- dist[i]=inf;
- memset(vis,false,sizeof(vis));
- q.push(s);
- dist[s]=0;
- while(!q.empty())
- {
- int u=q.front();
- q.pop();
- vis[u]=false;
- for(int i=head[u];i!=-1;i=e[i].next)
- {
- int v=e[i].to;
- if(dist[v]>dist[u]+e[i].w)
- {
- dist[v]=dist[u]+e[i].w;
- if(!vis[v])
- {
- vis[v]=true;
- q.push(v);
- }
- }
- }
- }
- }
- int main()
- {
- int a,b,c,s,e;
- scanf("%d%d",&n,&m);
- t=0;
- memset(head,-1,sizeof(head));
- while(m--)
- {
- scanf("%d%d%d",&a,&b,&c);
- add(a,b,c);
- }
- scanf("%d%d",&s,&e);
- spfa(s);
- if(dist[e]==inf) printf("-1\n");
- else printf("%d\n",dist[e]);
- return 0;
- }
- // 摘自 https://blog.csdn.net/ehi11/article/details/7927058
- BellmanFord:
- #include
- #include
- #include
- #include
- #define mem(a,b) memset(a,b,sizeof(a))
- #define For(a,b) for(int a=0;a<b;a++)
- using namespace std;
- const int maxn = 1e4;
- const int INF = 0x3f3f3f3f;
- const int inf = 0x3f;
- int dis[maxn];
- struct edge{
- int s,e; /// 起点, 终点
- int w; /// 权值
- }e[maxn];
- int n,m; //n 为点, m 为边的总数
- bool bellman(int a,int n) /// 求 a-> 其他点的最短路, n 为结点总数. 可判负环
- {
- memset(dis,inf,(n+1)<<2);
- dis[a]=0;
- For(i,n-1)
- For(j,m)
- dis[e[j].e]=min(dis[e[j].e],dis[e[j].s]+e[j].w); /// 松弛操作
- For(i,m) /// 松弛完后还能再松弛即代表有负环
- if(dis[e[i].e]>dis[e[i].s]+e[i].w)
- return true;
- return false;
- }
- int main()
- {
- cin>>n>>m;
- For(i,m)
- cin>>e[i].s>>e[i].e>>e[i].w;
- if(bellman(1,n))
- cout << "有负环" << endl;
- else
- for(int i=1;i<=n;i++){
- if(dis[i]!=INF)
- cout<< dis[i] << endl;
- else
- cout <<"INF" << endl;
- }
- }
- // 摘自 https://blog.csdn.net/bestsort/article/details/80100039
来源: http://www.bubuko.com/infodetail-3134416.html