Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 4052K 63MS Dijkstra 就是这么神奇(＾－＾)V 啥？为什么不用Floyd？没错，因为它超时了= - =

Posted by Pandorahearts at 2019-08-11 15:22:28 on Problem 2387 and last updated at 2019-08-11 15:23:48
```#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <map>
using namespace std;
#define INF 0x3f3f3f
#define zero 1e-7

typedef long long ll;
const int N=1005;

int mp[N][N], dis[N];
bool vis[N]={false};

void Dijkstra(int n) {
vis[1]=true;
for(int i=1; i<=n; i++)
dis[i]=mp[1][i];
for(int i=1; i<n; i++) {
int mind=INF, temp=1;
for(int j=2; j<=n; j++) {
if(dis[j]<mind && !vis[j]) {
mind=dis[j];
temp=j;
}
}
vis[temp]=true;
for(int j=2; j<=n; j++) {
if(dis[temp]+mp[temp][j]<dis[j] && !vis[j])
dis[j]=dis[temp]+mp[temp][j];
}
}
return ;
}

int main() {
int t, n, a, b, d;
scanf("%d %d", &t, &n);
for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) mp[i][j]=(i==j ? 0 : INF);
while(t--) {
scanf("%d %d %d", &a, &b, &d);
if(d<mp[a][b])
mp[a][b]=mp[b][a]=d;
}
Dijkstra(n);
printf("%d\n", dis[n]);
return 0;
}
```

Followed by: