dp

此题不用图论

同一个程序(dijkstra)

c++流输入输出

编译通过...

├ 测试数据 01：答案正确... 962ms

├ 测试数据 02：运行超时...

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：运行超时...

├ 测试数据 05：答案正确... 9ms

├ 测试数据 06：运行超时...

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 244ms

├ 测试数据 09：答案正确... 25ms

├ 测试数据 10：运行超时...

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：60 有效耗时：1240ms

c++标准输入输出

编译通过...

├ 测试数据 01：答案正确... 9ms

├ 测试数据 02：答案正确... 181ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 181ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 134ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 134ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：639ms

这就是差距!

怎么没有范围啊？

还能这样啊？？？？？

。。。。。

BD +1

这题估计描述的还好吧……

Dijkstra
```

Code Block

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
const int MAX = 1000 + 7;
const int INF = 0x3f3f3f3f;
int n;
int t;
int ans;
int a[MAX][MAX];
int d[MAX];//the shortest path
int pre[MAX];
vector<int> path;//路径还原
struct node
{
int to, cost;
node(int a = 0, int b = 0) : to(a), cost(b){}

};
vector<node> g[MAX];
priority_queue<P, vector<P>, greater<P> > q;

void dijkstra(int s)
{
fill(pre, pre + n + 1, -1);//
fill(d, d + n + 1, INF);//
d[s] = 0;
q.push(P(0, s));
while(!q.empty())
{
P p = q.top();
q.pop();
int v = p.second;
if(d[v] < p.first)
continue;
for(unsigned i = 0; i < g[v].size(); i++)
{
node e = g[v][i];
if(d[e.to] > d[v] + e.cost)
{
d[e.to] = d[v] + e.cost;
pre[e.to] = v;
q.push(P(d[e.to], e.to));
}
}
}
//ans = d[n];
}

vector<int> getpath(int t)
{
for(; t != - 1; t = pre[t])
path.push_back(t);
reverse(path.begin(), path.end());
return path;
}

int main()
{
#ifndef DEBUG
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
#endif

scanf("%d\n", &n);
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
scanf("%d", &t);
if(t != 0)
g[i].push_back(node(j, t));
}
}

dijkstra(1);
vector<int> path;

path = getpath(n);

for(unsigned i = 0; i < path.size(); i++)
cout<<path[i]<<" ";
printf("\n");
printf("%d\n", d[n]);
return 0;
}
```
Noip之前攒RP

Pascal转C++第一天刷题：
裸SPFA。
至于路径嘛。。开个数组记录一下就好了。。也可以最后看一遍dis数组。。
```c++
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;

const int maxspot=200010;
struct data
{
int v,next,last,z;
};

data a[4000010];
int front[maxspot],dis[maxspot],f[maxspot],h[maxspot],ans[maxspot];
int n,tot,tmp;

int relax(int x,int y,int tmp)
{
if (dis[x]+a[tmp].z<dis[y])
{
dis[y]=dis[x]+a[tmp].z;
front[y]=x;
return 1;
}
return 0;

}

void SPFA(int s,int t)
{
for (int i=1;i<=n;i++)
{
f[i]=1;
dis[i]=1e9;
}
dis[s]=0; h[1]=s; f[s]=0;
int top=0,bot=1;

while (top!=bot)
{
top++;
if (top==maxspot) top=1;
int x=h[top];
int tmp=a[x].last;
while (tmp)
{
int y=a[tmp].v;
if (relax(x,y,tmp)&&f[y])
{
bot++;
if (bot==maxspot) bot=1;
h[bot]=y;
f[y]=0;
}
tmp=a[tmp].next;
}
f[x]=1;
}
}

void build(int x,int y,int z)
{
a[++tot].v=y;
a[tot].next=a[x].last;
a[x].last=tot;
a[tot].z=z;
}

int main()
{
cin>>n;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
{
int x;
scanf("%d",&x);
if (x) build(i,j,x);
}
SPFA(1,n);

int top=0;
tmp=n;
while (tmp!=0)
{
ans[++top]=tmp;
tmp=front[tmp];
}

for (int i=top;i>0;i--) printf("%d ",ans[i]);

cout<<endl;
cout<<dis[n]<<endl;
}
```