题意：n个点m条无向边，如果从起点0到终点n-1的最短路距离为dist，求最少删除多少条边使得图中不再存在最短路。最多删除多少条边使得图中仍然存在最短路。

思路：先用spfa求一次最短路，开一个road数组，road[i]表示从起点走到i点最短路径所经过的最少边数，然后第二问就是m-road[n-1]；再依据最短路的dist数组推断哪些边是最短路上的，用它们又一次构图。跑一遍网络流求最小割。比赛的时候没有在最短路上建边，直接用的原图。果断TLE，又坑了队友=-=

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#pragma comment (linker,"/STACK:102400000,102400000")
#define pi acos(-1.0)
#define eps 1e-6
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define FRE(i,a,b)  for(i = a; i <= b; i++)
#define FREE(i,a,b) for(i = a; i >= b; i--)
#define FRL(i,a,b)  for(i = a; i < b; i++)
#define FRLL(i,a,b) for(i = a; i > b; i--)
#define mem(t, v)   memset ((t) , v, sizeof(t))
#define sf(n)       scanf("%d", &n)
#define sff(a,b)    scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define pf          printf
#define DBG         pf("Hi\n")
typedef long long ll;
using namespace std;

#define INF 0x3f3f3f3f
#define mod 1000000009
const int MAXN = 2005;
const int MAXM = 200005;
const int N = 1005;

int n,m;

struct EDGE
{
    int u,v,len,next;
}e[MAXM];

struct Edge
{
    int to,next,cap,flow;
}edge[MAXM];

int tol;
int head[MAXN];

void init()
{
    tol=0;
    memset(head,-1,sizeof(head));
}

void add(int u,int v,int len)
{
    e[tol].u=u;
    e[tol].v=v;
    e[tol].len=len;
    e[tol].next=head[u];
    head[u]=tol++;
    e[tol].u=v;
    e[tol].v=u;
    e[tol].len=len;
    e[tol].next=head[v];
    head[v]=tol++;
}

void addedge(int u,int v,int w,int rw=0)
{
    edge[tol].to=v;
    edge[tol].cap=w;
    edge[tol].flow=0;
    edge[tol].next=head[u];
    head[u]=tol++;

    edge[tol].to=u;
    edge[tol].cap=rw;
    edge[tol].flow=0;
    edge[tol].next=head[v];
    head[v]=tol++;
}

int Q[MAXN];
int dep[MAXN],cur[MAXN],sta[MAXN];

bool bfs(int s,int t,int n)
{
    int front=0,tail=0;
    memset(dep,-1,sizeof(dep[0])*(n+1));
    dep[s]=0;
    Q[tail++]=s;
    while (front<tail)
    {
        int u=Q[front++];
        for (int i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].to;
            if (edge[i].cap>edge[i].flow && dep[v]==-1)
            {
                dep[v]=dep[u]+1;
                if (v==t) return true;
                Q[tail++]=v;
            }
        }
    }
    return false;
}

int dinic(int s,int t,int n)
{
    int maxflow=0;
    while (bfs(s,t,n))
    {
        for (int i=0;i<n;i++) cur[i]=head[i];
        int u=s,tail=0;
        while (cur[s]!=-1)
        {
            if (u==t)
            {
                int tp=INF;
                for (int i=tail-1;i>=0;i--)
                    tp=min(tp,edge[sta[i]].cap-edge[sta[i]].flow);
                maxflow+=tp;
                for (int i=tail-1;i>=0;i--)
                {
                    edge[sta[i]].flow+=tp;
                    edge[sta[i]^1].flow-=tp;
                    if (edge[sta[i]].cap-edge[sta[i]].flow==0)
                        tail=i;
                }
                u=edge[sta[tail]^1].to;
            }
            else if (cur[u]!=-1 && edge[cur[u]].cap > edge[cur[u]].flow &&dep[u]+1==dep[edge[cur[u]].to])
            {
                sta[tail++]=cur[u];
                u=edge[cur[u]].to;
            }
            else
            {
                while (u!=s && cur[u]==-1)
                    u=edge[sta[--tail]^1].to;
                cur[u]=edge[cur[u]].next;
            }
        }
    }
    return maxflow;
}

int dist[MAXN];
int vis[MAXN];
int road[MAXN];

void SPFA()
{
    memset(vis,0,sizeof(vis));
    memset(dist,INF,sizeof(dist));
    memset(road,INF,sizeof(road));
    dist[0]=0;
    road[0]=0;
    vis[0]=1;
    queue<int>Q;
    Q.push(0);
    while (!Q.empty())
    {
        int u=Q.front();
        Q.pop();
        vis[u]=0;
        for (int i=head[u];~i;i=e[i].next)
        {
            int v=e[i].v;
            if (dist[v]>dist[u]+e[i].len)
            {
                dist[v]=dist[u]+e[i].len;
                road[v]=road[u]+1;
                if (!vis[v])
                {
                    vis[v]=1;
                    Q.push(v);
                }
            }
            else if (dist[v]==dist[u]+e[i].len)
            {
                if (road[v]>road[u]+1)
                {
                    road[v]=road[u]+1;
                    if (!vis[v])
                    {
                        vis[v]=1;
                        Q.push(v);
                    }
                }
            }
        }
    }
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("C:/Users/lyf/Desktop/IN.txt","r",stdin);
#endif
    int i,j,u,v,w;
    while (~sff(n,m))
    {
        init();
        for (i=0;i<m;i++)
        {
            sfff(u,v,w);
            if (u==v) continue;
            u--;v--;
            add(u,v,w);
        }
        SPFA();
        int cnt=tol;
        init();
        for (i=0;i<cnt;i++)
        {
            u=e[i].u;
            v=e[i].v;
            if (dist[v]==dist[u]+e[i].len)
                addedge(u,v,1);
        }
        int ans=dinic(0,n-1,n);
        pf("%d %d\n",ans,m-road[n-1]);
    }
    return 0;
}