# interestingLSY 的博客

### 题解 P3371 【【模板】单源最短路径】

posted on 2016-11-18 19:37:28 | under 题解 |

# 代码


#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#include <vector>
#include <string.h>
using namespace std;
#define uint unsigned int
#define ll long long
#define ull unsigned ll
#define pii pair<int,int>
#define pb push\_back
#define mp make\_pair
#define INF 2147483647
#define LINF 9999999999
#define ms(l) memset(l,0,sizeof(l))

uint n,m,spoint;
uint dis[10001];
class Edge{
public:
uint to,cost;
};
vector<Edge> data[10000];

Edge e1;
e1.to = to; e1.cost = co;
data[fr].pb(e1);
}

void spfa(void){
queue<uint> q;        bool at[10001];
q.push(spoint);        ms(at);
for(uint i = 1;i <= n;i++)
dis[i] = INF;
dis[spoint] = 0;    at[spoint] = 1;
while(!q.empty()){
uint u;
u = q.front();
q.pop();            at[u] = 0;
for(uint i = 0;i < data[u].size();i++)
if(dis[u]+data[u][i].cost < dis[data[u][i].to]){
dis[data[u][i].to] = dis[u]+data[u][i].cost;
if(!at[data[u][i].to]){
at[data[u][i].to] = 1;
q.push(data[u][i].to);
}
}
}
}
int main(){
//freopen("i.txt","r",stdin);
cin >> n >> m >> spoint;
for(uint i = 1;i <= m;i++){
uint f,t,c;
cin >> f >> t >> c;
}