WA了多次.因為構圖時少打了個=號....
枚舉最高rank,多次構圖,然后就最短路 O(N^3)
以后要注意靜態調試
#include <iostream>
//#include <fstream>
#include <math.h>
using namespace std;
//ifstream fin("t1062.in");
const int MAXN=101;
#define INF 2147483647
int p[MAXN],l[MAXN],x;
int u[MAXN][MAXN];
int q[MAXN];
int m,n;
void dijkstra()
{
int dist[MAXN];
bool hash[MAXN];
int answer=INF;
for (int i=n;i>=1;--i)
{
int maxRank=l[i];
for (int j=1;j<=n;++j)
if (l[j]>maxRank||maxRank-l[j]>m) q[j]=1;
else q[j]=0;
memset(hash,0,sizeof(hash));
for (int j=1;j<=n;++j)
dist[j]=p[j];
for (int j=1;j<=n;++j)
{
int u1=0;
int min=INF;
for (int k=1;k<=n;++k)
{
if (q[k]) continue;
if (hash[k]) continue;
if (min>dist[k]) {min=dist[k];u1=k;}
}
hash[u1]=true;
if (u1==0) break;
if (dist[u1]==0x7f) break;
for (int k=1;k<=n;++k)
{
if (q[k]) continue;
if (u[u1][k]==0x7f) continue;
if (dist[k]>dist[u1]+u[u1][k])
{
dist[k]=dist[u1]+u[u1][k];
}
}
}
if (answer>dist[1]) answer=dist[1];
}
cout<<answer<<endl;
}
int main()
{
memset(u,0x7f,sizeof(u));
cin>>m>>n;
for (int i=1;i<=n;i++)
{
cin>>p[i]>>l[i]>>x;
for (int j=1;j<=x;j++)
{
int t,v;
cin>>t>>v;
u[t][i]=v;
}
}
dijkstra();
return 0;
}