90分，不知道错在哪里了，dijkstra算法，用一个数组的d[i]表示以i点结尾的小路的长度，以i点为中心扩展时，若下一点为k，如果i->k是小路，则d[j] = d[k]+M[k][j];dist[j] = min_ - pow(d[k], 2) + pow(d[j], 2);
否则直接加路径长度即可，同时把d[j]=0
#include <iostream>
#include <cstdio>
#include <climits>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 100000000;
const int MAXN = 505;
int M[MAXN][MAXN];
int kind[MAXN][MAXN];
int dijkstra(int n)
{
int flag[MAXN];
long long dist[MAXN];
int k;
int d[MAXN];
memset(flag, 0, sizeof(flag));
memset(d, 0, sizeof(d));
for (int i = 0; i < n; i++)
{
if (M[0][i] > 0)
{
if (kind[0][i] == 0)
dist[i] = M[0][i];
else
{
dist[i] = pow(M[0][i], 2);
d[i] = M[0][i];
}
}
else
dist[i] = -1;
}
flag[0] = 1;
dist[0] = 0;
for (int i = 1; i < n; i++)
{
int min_ = INF;
for (int j = 0; j < n; j++)
{
if (!flag[j]&&dist[j]>0&&dist[j]<min_)
{
min_ = dist[j];
k = j;
}
}
flag[k] = 1;
for (int j = 0; j < n; j++)
{
if (!flag[j] && M[j][k]>0)
{
if (dist[j] < 0)
{
if (kind[k][j] == 0)
{
d[j] = 0;
dist[j] = min_ + M[j][k];
}
else
{
d[j] = d[k]+M[j][k];
dist[j] = min_ - pow(d[k], 2) + pow(d[k] + M[j][k],2);
}
continue;
}
if (dist[j] > 0)
{
if (kind[k][j] == 0)
{
if (dist[j] > min_ + M[j][k])
{
dist[j] = min_ + M[j][k];
d[j] = 0;
}
}
else
{
int temp = min_ - pow(d[k], 2) + pow(d[k] + M[k][j], 2);
if (dist[j] > (min_ - pow(d[k], 2) + pow(d[k]+M[k][j], 2)))
{
d[j] = d[k]+M[k][j];
dist[j] = min_ - pow(d[k], 2) + pow(d[j], 2);
}
}
continue;
}
}
}
}
return dist[n-1];
}
int main()
{
int n, m;
while (~scanf("%d %d",&n,&m))
{
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (i == j)M[i][j] = 0;
else M[i][j] = -1;
memset(kind, 0, sizeof(kind));
for (int i = 0; i < m; i++)
{
int k, a, b, c;
scanf("%d %d %d %d", &k, &a, &b, &c);
M[a-1][b-1] = M[b-1][a-1] = c;
kind[a-1][b-1] = kind[b-1][a-1] = k;
}
cout<<dijkstra(n)<<endl;
}
return 0;
}