[CCF 201712-4] Driving route (Dijkstra 80 points)

Ignore a condition: may have a continuous path, run a naked Dijkstra algorithm, you can get 80 points

Note: Boundary rights may explode int, long long can be used

#include <iostream>
#include <cstring>
Using namespace std;

Const long long inf = 1e14;
Long long edge[505][505]; //the length of the edge
Bool vis[505]; //Is the length of the shortest path determined?
Long long d[505]; //the length of the shortest path
Long long cur,a,b,c,n,m,flag,imin;

Void init()
{
Memset(edge,0,sizeof(edge));
Memset(vis,0,sizeof(vis));

For(int i=1; i<=n; ++i)
d[i] = inf;

Vis[1] = cur = 1;
d[1] = 0;

For(int i=0; i<m; ++i) //Process the length of each side
{
Cin>>flag>>a>>b>>c;
If(flag == 1) c *= c;
If(edge[a][b]==0 || c < edge[a][b])
Edge[a][b] = edge[b][a] = c;
}
}

Int main()
{
Cin>>n>>m;
Init();
For(int i=1; i<=n-1; ++i) //To join n-1 nodes again
{
For(int j=1; j<=n; ++j) //relax each edge of the current node
{
If(vis[j]==0 && edge[cur][j] && edge[cur][j] + d[cur] < d[j])
d[j] = edge[cur][j] + d[cur];
}

Imin = inf;
For(int j=1; j<=n; ++j) // find the node with the smallest d value
{
If(vis[j]==0 && imin > d[j])
{
Imin = d[j];
Cur = j;
}
}
Vis[cur] = 1;
If(cur==n) break; //the shortest path of node n is found, exit
}

Cout<<d[n];
Return 0;
}