C--最短路
Time Limit: 7000 ms Memory Limit: 65536 KiB
Submit Statistic Discuss
Problem Description
给出一个带权无向图，包含n个点，m条边。求出s，e的最短路。保证最短路存在。
Input
多组输入。
对于每组数据。
第一行输入n，m(1<= n && n<=5*10^5,1 <= m && m <= 3*10^6)。
接下来m行，每行三个整数，u,v,w,表示u，v之间有一条权值为w(w >= 0)的边。
最后输入s，e。
Output
对于每组数据输出一个整数代表答案。
Sample Input
3 1 1 2 3 1 2
Sample Output
3
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 500001;
const int inf = 0x3f3f3f3f;
int n, m;
int vis[maxn];
int dis[maxn];struct node
{int to;int w;
};
vector<node>vec[maxn];
void spfa(int sc, int st)
{memset(vis, 0, sizeof(vis));memset(dis, inf, sizeof(dis));vis[sc] = 1;dis[sc] = 0;queue<int>q;q.push(sc);while(!q.empty()){int now = q.front();q.pop();vis[now] = 0;for(int i = 0; i < vec[now].size(); i++){int to = vec[now][i].to;int w = vec[now][i].w;if(dis[to] > dis[now] + w){dis[to] = dis[now] + w;if(!vis[to]){q.push(to);vis[to]=1;}}}}printf("%d\n",dis[st]);
}
int main()
{while(~scanf("%d%d", &n, &m)){for(int i = 1; i <= n; i++)vec[i].clear();for(int i = 1; i <= m; i++){int u,v,w;scanf("%d%d%d", &u, &v, &w);node tmp;tmp.to = v;tmp.w = w;vec[u].push_back(tmp);tmp.to=u;tmp.w=w;vec[v].push_back(tmp);}int sc,st;scanf("%d%d", &sc, &st);spfa(sc, st);}return 0;
}