做第一道查分约束poj 3159...TLE不断。估计管理员是跟C++的STL过不去,就卡用vector的人了。。而我已经好久好久没人工写什么邻接表,前向星什么的了,就只能TLE过不了了。。换了什么dijkstra+优先队列,SPFA+stack优化,只要用vector来存边,估计都过不了。
下面是TLE代码,留纪念。
#include <string.h>
#include <stdio.h>
#include <vector>
using namespace std;
int n, m;
int dis[30001];
bool visit[30001];
int S[30001], S_top = 0;
vector<int> vert[30001], edge[30001];
void dijkstra(int s);
int main()
{
    int u,v,w;
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; i++) {
        scanf("%d%d%d", &u, &v, &w);
        vert[u].push_back(v);
        edge[u].push_back(w);
    }
    dijkstra(1);    //最长路-----不是的,是最短路!
    printf("%d\n", dis[n]);
}
void dijkstra(int s)
{
    memset(dis, 127, sizeof(dis));
    dis[s] = 0;
    visit[s] = true;
    S[++S_top] = s;
    while(S_top > 0) {
        int u = S[S_top--];
        visit[u] = false;
        for(int Size = vert[u].size(), i = 0; i < Size; i++) {
            int v = vert[u][i];
            if(dis[v] > dis[u] + edge[u][i]) {
                dis[v] = dis[u] + edge[u][i];
                if(visit[v] == false) {
                    S[++S_top] = v;
                    visit[v] = true;
                }
            }
       }
   }
}