南京网络赛 - L
Magical Girl Haze
There are N cities in the country, and MM directional roads from u to v(1≤u,v≤n). Every road has a distance ci. Haze is a Magical Girl that lives in City 1, she can choose no more than K roads and make their distances become 0. Now she wants to go to City N, please help her calculate the minimumdistance.
Input
The first line has one integer T(1≤T≤5), then following T cases.
For each test case, the first line has three integers N,M and K.
Then the following M lines each line has three integers, describe a road, Ui, Vi, Ci. There might be multiple edges between u and v.
It is guaranteed that N≤100000,M≤200000,K≤10,0≤Ci≤1e9. There is at least one path between City 1 and City N.
Output
For each test case, print the minimum distance.
样例输入
1
5 6 1
1 2 2
1 3 4
2 4 3
3 4 1
3 5 6
4 5 2
样例输出
3
分析：
求最短路，可以选择k个边权变为0，是分层图最短路的板子题。抄板子一直不过，可能会有两个问题，一个是没开longlong，一个是我把单向边存成了双向边，找了我好久。网上很多题解说要去重边，而实际上根本不需要，对结果没有任何影响。还有就是数组尽量开大，防止段错误。
参考代码：
模板1：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
typedef long long ll;
#define pii pair<ll,int>
const ll inf=0x3f3f3f3f;
const int MAXN=4500005;
using namespace std;struct Edge {
int to,next;ll w;
} edge[MAXN];
int head[MAXN],tot;
ll dis[MAXN],ans;
int vis[MAXN];
int n,m,s,t,k;void init() {
tot=0;memset(head,-1,sizeof(head));memset(dis,inf,sizeof(dis));memset(vis,0,sizeof(vis));
}void addedge(int u,int v,ll w) {
edge[tot].to=v;edge[tot].w=w;edge[tot].next=head[u];head[u]=tot++;
}void dijkstra() {
priority_queue<pii,vector<pii>,greater<pii> > q;dis[s]=0; q.push({
dis[s],s});while(!q.empty()) {
int now=q.top().second;q.pop();if (vis[now]) continue;vis[now]=1;for (int i=head[now];i!=-1;i=edge[i].next) {
int v=edge[i].to;if(!vis[v]&&dis[v]>dis[now]+edge[i].w) {
dis[v]=dis[now]+edge[i].w;q.push({
dis[v],v});}}}
}int main() {
int T,u,v; ll w;scanf("%d",&T);while(T--) {
init();cin >> n >> m >> k;// 起点为1，终点为ns=1; t=n;for (int i=1;i<=m;i++) {
scanf("%d%d%lld",&u,&v,&w);for (int j=0;j<=k;j++) {
// 双向边就GG，不需要去重边addedge(u+j*n,v+j*n,w);//addedge(v+j*n,u+j*n,w);if (j!=k) {
addedge(u+j*n,v+(j+1)*n,0);//addedge(v+j*n,u+(j+1)*n,0);}}}ans=1e18;dijkstra();for (int i=0;i<=k;i++)ans=min(ans,dis[t+i*n]);cout << ans << endl;}return 0;
}
模板2：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
typedef long long ll;
#define pii pair<ll, int>
const ll inf=0x3f3f3f3f;
const int MAXN=300005;
using namespace std;struct node {
int x,y;ll w;node(){
}node(int _x,int _y,ll _w) {
x=_x; y=_y; w=_w;}friend bool operator < (const node a,const node b) {
return a.w > b.w;}
};
struct Edge {
int to,next;ll w;
} edge[MAXN*4];
int head[MAXN*4],tot;
ll dis[MAXN][15],ans;
int vis[MAXN][15];
int n,m,s,t,k;void init() {
tot=0;memset(head,-1,sizeof(head));memset(dis,inf,sizeof(dis));memset(vis,0,sizeof(vis));
}void addedge(int u,int v,ll w) {
edge[tot].to=v;edge[tot].w=w;edge[tot].next=head[u];head[u]=tot++;
}void dijkstra() {
priority_queue<node> q;dis[s][0]=0;q.push(node(s,0,0));while(!q.empty()) {
int x=q.top().x,y=q.top().y;q.pop();if (vis[x][y]) continue;vis[x][y]=1;for (int i=head[x];i!=-1;i=edge[i].next) {
int to=edge[i].to;if (dis[x][y]+edge[i].w<dis[to][y]) {
dis[to][y]=dis[x][y]+edge[i].w;q.push(node(to,y,dis[to][y]));}if (y+1<=k && dis[x][y]<dis[to][y+1]) {
dis[to][y+1]=dis[x][y];q.push(node(to,y+1,dis[to][y+1]));}}}
}int main() {
int T,u,v; ll w;scanf("%d",&T);while(T--) {
init();cin >> n >> m >> k;s=1; t=n;for (int i=1;i<=m;i++) {
scanf("%d%d%lld",&u,&v,&w);addedge(u,v,w);}ans=1e18;dijkstra();for (int i=0;i<=k;i++)ans=min(ans,dis[n][i]);cout << ans << endl;}return 0;
}